A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching. (English) Zbl 1448.90043
Summary: We study the parallel machine scheduling problem to minimize the sum of the weighted completion times of the jobs to be scheduled (problem \(Pm \parallel \sum w_j C_j\) in the standard three-field notation). We use the set covering formulation that was introduced by J. M. van den Akker et al. [Oper. Res. 47, No. 6, 862–872 (1999; Zbl 0979.90051)] for this problem, and we improve the computational performance of their branch-and-price (B&P) algorithm by a number of techniques, including a different generic branching scheme, zero-suppressed binary decision diagrams (ZDDs) to solve the pricing problem, dual-price smoothing as a stabilization method, and Farkas pricing to handle infeasibilities. We report computational results that show the effectiveness of the algorithmic enhancements, which depends on the characteristics of the instances. To the best of our knowledge, we are also the first to use ZDDs to solve the pricing problem in a B&P algorithm for a scheduling problem.
The online supplement is available at https://doi.org/10.1287/ijoc.2018.0809.
The online supplement is available at https://doi.org/10.1287/ijoc.2018.0809.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
parallel machine scheduling; weighted completion times; branch-and-price; ZDD; stabilizationCitations:
Zbl 0979.90051References:
| [1] | Agarwal Y, Mathur K, Salkin H (1989) A set-partitioning-based exact algorithm for the vehicle routing problem. Networks 19(7):731-749.Crossref, Google Scholar · Zbl 0682.90050 · doi:10.1002/net.3230190702 |
| [2] | Akers S (1978) Binary decision diagrams. IEEE Trans. Comput. 100(6):509-516.Crossref, Google Scholar · Zbl 0377.94038 · doi:10.1109/TC.1978.1675141 |
| [3] | Azizoglu M, Kirca O (1999) On the minimization of total weighted flow time with identical and uniform parallel machines. Eur. J. Oper. Res. 113(1):91-100.Crossref, Google Scholar · Zbl 0933.90025 · doi:10.1016/S0377-2217(97)00427-X |
| [4] | Belouadah H, Potts C (1994) Scheduling identical parallel machines to minimize total weighted completion time. Discrete Appl. Math. 48(3):201-218.Crossref, Google Scholar · Zbl 0809.90073 · doi:10.1016/0166-218X(92)00176-M |
| [5] | Ben-Ameur W, Neto J (2007) Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks 49(1):3-17.Crossref, Google Scholar · Zbl 1131.90047 · doi:10.1002/net.20137 |
| [6] | Bergman D, Cire A, van Hoeve WJ, Hooker J (2016) Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1):47-66.Link, Google Scholar · Zbl 1338.90260 |
| [7] | Bigras LP, Gamache M, Savard G (2008) Time-indexed formulations and the total weighted tardiness problem. INFORMS J. Comput. 20(1):133-142.Link, Google Scholar · Zbl 1243.90057 |
| [8] | Bruno J, Coffman EJ, Sethi R (1974) Scheduling independent tasks to reduce mean finishing time. Comm. ACM 17(7):382-387.Crossref, Google Scholar · Zbl 0283.68039 · doi:10.1145/361011.361064 |
| [9] | Bülbül K, Şen H (2017) An exact extended formulation for the unrelated parallel machine total weighted completion time problem. J. Scheduling 20(4):373-389.Crossref, Google Scholar · Zbl 1375.90118 · doi:10.1007/s10951-016-0485-x |
| [10] | Chen ZL, Powell W (1999) Solving parallel machine scheduling problems by column generation. INFORMS J. Comput. 11(1):78-94.Link, Google Scholar · Zbl 1034.90506 |
| [11] | Cire A, van Hoeve WJ (2013) Multivalued decision diagrams for sequencing problems. Oper. Res. 61(6):1411-1428.Link, Google Scholar · Zbl 1291.90091 |
| [12] | Dyer M, Wolsey L (1990) Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. 26(2):255-270.Crossref, Google Scholar · Zbl 0694.90060 · doi:10.1016/0166-218X(90)90104-K |
| [13] | Elmaghraby S, Park S (1974) Scheduling jobs on a number of identical machines. AIIE Trans. 6(1):1-13.Crossref, Google Scholar · doi:10.1080/05695557408974926 |
| [14] | Fukasawa R, Longo H, Lysgaard J, de Aragão M, Reis M, Uchoa E, Werneck R (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491-511.Crossref, Google Scholar · Zbl 1094.90050 · doi:10.1007/s10107-005-0644-x |
| [15] | Held S, Cook W, Sewell E (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363-381.Crossref, Google Scholar · Zbl 1267.90005 · doi:10.1007/s12532-012-0042-3 |
| [16] | Hooker J (2013) Decision diagrams and dynamic programming. Gomes C, Sellmann M, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Berlin), 94-110.Google Scholar · Zbl 1382.90113 |
| [17] | Iwashita H, Minato SI (2013) Efficient top-down ZDD construction techniques using recursive specifications. Technical Report TCS-TR-A-13-69, Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan.Google Scholar |
| [18] | Knuth DE (2011) The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 (Addison-Wesley, Upper Saddle River, NJ).Google Scholar · Zbl 1354.68001 |
| [19] | Lawler E, Moore J (1969) A functional equation and its application to resource allocation and sequencing problems. Management Sci. 16(1):77-84.Link, Google Scholar · Zbl 0184.23303 |
| [20] | Lee CY (1959) Representation of switching circuits by binary-decision programs. Bell System Tech. J. 38(4):985-999.Crossref, Google Scholar · Zbl 0222.94042 · doi:10.1002/j.1538-7305.1959.tb01585.x |
| [21] | Lee CY, Uzsoy R (1992) A new dynamic programming algorithm for the parallel machines total weighted completion time problem. Oper. Res. Lett. 11(2):73-75.Crossref, Google Scholar · Zbl 0760.90057 · doi:10.1016/0167-6377(92)90035-2 |
| [22] | Lenstra J, Rinnooy Kan A, Brucker P (1977) Complexity of machine scheduling problems. Ann. Discrete Math. 1:343-362.Crossref, Google Scholar · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X |
| [23] | Lopes M, de Carvalho J (2007) A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times. Eur. J. Oper. Res. 176(3):1508-1527.Crossref, Google Scholar · Zbl 1113.90061 · doi:10.1016/j.ejor.2005.11.001 |
| [24] | Mehrotra A, Trick M (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8(4):344-354.Link, Google Scholar · Zbl 0884.90144 |
| [25] | Minato SI (1993) Zero-suppressed BDDs for set manipulation in combinatorial problems. Proc. 30th Internat. Design Automation Conf. (Association for Computing Machinery, New York), 272-277.Crossref, Google Scholar · doi:10.1145/157485.164890 |
| [26] | Morrison D, Sewell E, Jacobson S (2016a) Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams. INFORMS J. Comput. 28(1):67-82.Link, Google Scholar · Zbl 1338.90431 |
| [27] | Morrison D, Jacobson S, Sauppe J, Sewell E (2016b) Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19:79-102.Crossref, Google Scholar · Zbl 1387.90010 · doi:10.1016/j.disopt.2016.01.005 |
| [28] | Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2015) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339-360.Link, Google Scholar · Zbl 1528.90164 |
| [29] | Pessoa A, Uchoa E, de Aragão M, Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2(3-4):259-290.Crossref, Google Scholar · Zbl 1208.90119 · doi:10.1007/s12532-010-0019-z |
| [30] | Rothkopf M (1966) Scheduling independent tasks on parallel processors. Management Sci. 12(5):437-447.Link, Google Scholar |
| [31] | Ryan D, Foster B (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269-280.Google Scholar |
| [32] | Sadykov R, Vanderbeck F (2013) Column generation for extended formulations. EURO J. Computational Optim. 1(1-2):81-115.Crossref, Google Scholar · Zbl 1305.90312 · doi:10.1007/s13675-013-0009-9 |
| [33] | Smith W (1956) Various optimizers for single-stage production. Naval Res. Logist. Quart. 3(1-2):59-66.Crossref, Google Scholar · doi:10.1002/nav.3800030106 |
| [34] | van den Akker J, Hoogeveen J, van de Velde S (1999) Parallel machine scheduling by column generation. Oper. Res. 47(6):862-872.Link, Google Scholar · Zbl 0979.90051 |
| [35] | van den Akker J, Hoogeveen H, van de Velde S (2002) Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem. INFORMS J. Comput. 14(1):37-51.Link, Google Scholar · Zbl 1238.90096 |
| [36] | van den Akker J, Hurkens C, Savelsbergh M (2000) Time-indexed formulations for machine scheduling problems: Column generation. INFORMS J. Comput. 12(2):111-124.Link, Google Scholar · Zbl 1034.90004 |
| [37] | Vance P, Barnhart C, Johnson E, Nemhauser G (1994) Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl. 3(2):111-130.Crossref, Google Scholar · Zbl 0801.90080 · doi:10.1007/BF01300970 |
| [38] | Webster S (1992) New bounds for the identical parallel processor weighted flow time problem. Management Sci. 38(1):124-136.Link, Google Scholar · Zbl 0777.90020 |
| [39] | Wentges P (1997) Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming. Internat. Trans. Oper. Res. 4(2):151-162.Crossref, · Zbl 0886.90107 · doi:10.1111/j.1475-3995.1997.tb00071.x |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
