×

Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization. (English) Zbl 1487.90302

Summary: This paper addresses the parallel machine scheduling problem with family dependent setup times and total weighted completion time minimization. In this problem, when two jobs \(j\) and \(k\) are scheduled consecutively on the same machine, a setup time is performed between the finishing time of \(j\) and the starting time of \(k\) if and only if \(j\) and \(k\) belong to different families. The problem is strongly \(\mathcal{NP} \)-hard and is commonly addressed in the literature by heuristic approaches and by branch-and-bound algorithms. Achieving proven optimal solution is a challenging task even for small size instances. Our contribution is to introduce five novel mixed integer linear programs based on concepts derived from one-commodity, arc-flow and set covering formulations. Numerical experiments on more than 13000 benchmark instances show that one of the arc-flow models and the set covering model are quite efficient, as they provide on average better solutions than state-of-the-art approaches, with shorter computation times, and solve to proven optimality a large number of open instances from the literature.

MSC:

90B35 Deterministic scheduling theory in operations research

References:

[1] Allahverdi, A., The third comprehensive survey on scheduling problems with setup times/costs, European Journal of Operational Research, 246, 2, 345-378 (2015) · Zbl 1347.90031
[2] Allahverdi, A.; Ng, C.; Cheng, T.; Kovalyov, M. Y., A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187, 3, 985-1032 (2008) · Zbl 1137.90474
[3] Azizoglu, M.; Kirca, O., On the minimization of total weighted flow time with identical and uniform parallel machines, European Journal of Operational Research, 113, 1, 91-100 (1999) · Zbl 0933.90025
[4] Azizoglu, M.; Webster, S., Scheduling parallel machines to minimize weighted flowtime with family set-up times, International Journal of Production Research, 41, 6, 1199-1215 (2003) · Zbl 1063.90025
[5] Bettayeb, B.; Kacem, I.; Adjallah, K. H., An improved branch-and-bound algorithm to minimize the weighted flowtime on identical parallel machines with family setup times, Journal of Systems Science and Systems Engineering, 17, 4, 446-459 (2008)
[6] Bruck, B. P.; Iori, M., Non-elementary formulations for single vehicle routing problems with pickups and deliveries, Operations Research, 65, 6, 1597-1614 (2017) · Zbl 1382.90006
[7] Bruno, J.; Coffman, E. G., Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, 17, 7, 382-387 (1974) · Zbl 0283.68039
[8] Chen, Z.-L.; Powell, W. B., Solving parallel machine scheduling problems by column generation, INFORMS Journal on Computing, 11, 1, 78-94 (1999) · Zbl 1034.90506
[9] Chen, Z.-L.; Powell, W. B., Exact algorithms for scheduling multiple families of jobs on parallel machines, Naval Research Logistics (NRL), 50, 7, 823-840 (2003) · Zbl 1044.90033
[10] Côté, J.-F.; Iori, M., The meet-in-the-middle principle for cutting and packing problems, INFORMS Journal on Computing, 30, 4, 646-661 (2018) · Zbl 1528.90211
[11] Crauwels, H.; Hariri, A.; Potts, C.; Van Wassenhove, L., Branch and bound algorithms for single-machine scheduling with batch set-up times to minimize total weighted completion time, Annals of Operations Research, 83, 0, 59-76 (1998) · Zbl 0913.90164
[12] Crauwels, H.; Potts, C.; Van Wassenhove, L., Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time, Annals of Operations Research, 70, 0, 261-279 (1997) · Zbl 0890.90095
[13] Delorme, M.; Iori, M.; Martello, S., Bin packing and cutting stock problems: Mathematical models and exact algorithms, European Journal of Operational Research, 255, 1, 1-20 (2016) · Zbl 1346.90700
[14] Dunstall, S.; Wirth, A., A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines, European Journal of Operational Research, 167, 2, 283-296 (2005) · Zbl 1074.90015
[15] Dunstall, S.; Wirth, A., Heuristic methods for the identical parallel machine flowtime problem with set-up times, Computers & Operations Research, 32, 9, 2479-2491 (2005) · Zbl 1116.90348
[16] Dunstall, S.; Wirth, A.; Baker, K., Lower bounds and algorithms for flowtime minimization on a single machine with set-up times, Journal of Scheduling, 3, 1, 51-69 (2000) · Zbl 0966.90031
[17] Elmaghraby, S. E.; Park, S. H., Scheduling jobs on a number of identical machines, AIIE Transactions, 6, 1, 1-13 (1974)
[18] Feillet, D., A tutorial on column generation and branch-and-price for vehicle routing problems, 4OR, 8, 4, 407-424 (2010) · Zbl 1208.90016
[19] Gavish, B.; Graves, S., The traveling salesman problem and related problems, Working Paper OR (1978), Operations Research Center, Massachusetts Institute of Technology
[20] Ghosh, J. B., Batch scheduling to minimize total completion time, Operations Research Letters, 16, 5, 271-275 (1994) · Zbl 0826.90063
[21] Gouveia, L.; Leitner, M.; Ruthmair, M., Layered graph approaches for combinatorial optimization problems, Computers & Operations Research, 102, 22-38 (2019) · Zbl 1458.90612
[22] Graham, R.; Lawler, E.; Lenstra, J.; Kan, A., Optimization and approximation in deterministic sequencing and scheduling: a survey, (P. L. Hammer, E. J.; Korte, B., Discrete optimization ii proceedings of the advanced research institute on discrete optimization and systems applications. Discrete optimization ii proceedings of the advanced research institute on discrete optimization and systems applications, Annals of Discrete Mathematics, 5 (1979), Elsevier), 287-326 · Zbl 0411.90044
[23] Hinder, O.; Mason, A. J., A novel integer programming formulation for scheduling with family setup times on a single machine to minimize maximum lateness, European Journal of Operational Research, 262, 2, 411-423 (2017) · Zbl 1375.90126
[24] Kowalczyk, D.; Leus, R., A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching, INFORMS Journal on Computing, 30, 4, 768-782 (2018) · Zbl 1448.90043
[25] Kramer, A.; Dell’Amico, M.; Iori, M., Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines, European Journal of Operational Research, 275, 1, 67-79 (2019) · Zbl 1430.90275
[26] Kramer, A.; Subramanian, A., A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems, Journal of Scheduling, 22, 1, 21-57 (2019) · Zbl 1425.90047
[27] Liao, C.-J.; Chao, C.-W.; Chen, L.-C., An improved heuristic for parallel machine weighted flowtime scheduling with family set-up times, Computers & Mathematics with Applications, 63, 1, 110-117 (2012) · Zbl 1238.90068
[28] Lübbecke, M. E.; Desrosiers, J., Selected topics in column generation, Operations Research, 53, 6, 1007-1023 (2005) · Zbl 1165.90578
[29] Macedo, R.; Alves, C.; de Carvalho, J. V., Arc-flow model for the two-dimensional guillotine cutting stock problem, Computers & Operations Research, 37, 6, 991-1001 (2010) · Zbl 1178.90292
[30] Macedo, R.; Alves, C.; de Carvalho de Carvalho, J. V.; Clautiaux, F.; Hanafi, S., Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model, European Journal of Operational Research, 214, 3, 536-545 (2011) · Zbl 1219.90022
[31] Mason, A. J.; Anderson, E. J., Minimizing flow time on a single machine with job classes and setup times, Naval Research Logistics (NRL), 38, 3, 333-350 (1991) · Zbl 0747.90049
[32] Monma, C. L.; Potts, C. N., On the complexity of scheduling with batch setup times, Operations Research, 37, 5, 798-804 (1989) · Zbl 0686.90025
[33] Mrad, M.; Souayah, N., An arc-flow model for the makespan minimization problem on identical parallel machines, IEEE Access, 6, 5300-5307 (2018)
[34] Nesello, V.; Delorme, M.; Iori, M.; Subramanian, A., Mathematical models and decomposition algorithms for makespan minimization in plastic rolls production, Journal of the Operational Research Society, 69, 3, 326-339 (2018)
[35] Pereira Lopes, M. J.; Valério de Carvalho, J., A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times, European Journal of Operational Research, 176, 3, 1508-1527 (2007) · Zbl 1113.90061
[36] Pessoa, A.; Uchoa, E.; de Aragão, M. P.; Rodrigues, R., Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems, Mathematical Programming Computation, 2, 3, 259-290 (2010) · Zbl 1208.90119
[37] Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: A review, European Journal of Operational Research, 120, 2, 228-249 (2000) · Zbl 0953.90028
[38] Salazar-González, J.-J.; Santos-Hernández, B., The split-demand one-commodity pickup-and-delivery travelling salesman problem, Transportation Research Part B: Methodological, 75, 58-73 (2015)
[39] Tseng, C.-T.; Lee, C.-H., A new electromagnetism-like mechanism for identical parallel machine scheduling with family setup times, The International Journal of Advanced Manufacturing Technology, 89, 5, 1865-1874 (2017)
[40] Unlu, Y.; Mason, S. J., Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems, Computers & Industrial Engineering, 58, 4, 785-800 (2010)
[41] Valério de Carvalho, J., Exact solution of bin-packing problems using column generation and branch-and-bound, Annals of Operations Research, 86, 0, 629-659 (1999) · Zbl 0922.90113
[42] van den Akker, J. M.; Hoogeveen, J. A.; van de Velde, S. L., Parallel machine scheduling by column generation, Operations Research, 47, 6, 862-872 (1999) · Zbl 0979.90051
[43] Velez, S.; Dong, Y.; Maravelias, C. T., Changeover formulations for discrete-time mixed-integer programming scheduling models, European Journal of Operational Research, 260, 3, 949-963 (2017) · Zbl 1403.90373
[44] Webster, S., The complexity of scheduling job families about a common due date, Operations Research Letters, 20, 2, 65-74 (1997) · Zbl 0890.90111
[45] Webster, S.; Azizoglu, M., Dynamic programming algorithms for scheduling parallel machines with family setup times, Computers & Operations Research, 28, 2, 127-137 (2001) · Zbl 0990.90052
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.