A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions. (English) Zbl 1487.90291
Summary: This paper addresses a parallel machine scheduling problem with restrictions on employees’ working-times and break times. Tasks must be processed by employees nonpreemptively on unrelated parallel machines with different thresholds that specify for each employee the maximum total and consecutive working-time, and the minimum break time. The objective is to minimize the weighted sum of the makespan, the machine depreciation costs, and the labor costs. To solve this problem, a mixed integer linear programming model is formulated, and two different decomposition-based exact algorithms are implemented as well as a list scheduling (LS)-based heuristic method. Extensive computational experiments are performed on randomly generated instances, and the results demonstrate the efficiency of our proposed combinatorial Benders decomposition approach.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C11 | Mixed integer programming |
| 90C27 | Combinatorial optimization |
Keywords:
scheduling; parallel machine; maximum consecutive working-time; minimum break time; combinatorial Benders decompositionReferences:
| [1] | Agnetis, A.; Murgia, G.; Sbrilli, S., A job shop scheduling problem with human operators in handicraft production, International Journal of Production Research, 52, 13, 3820-3831 (2014) |
| [2] | Ağralı, S.; Taşkın, Z. C.; Ünal, A. T., Employee scheduling in service industries with flexible employee availability and demand, Omega, 66, 159-169 (2017) |
| [3] | Ahmadi-Javid, A.; Hooshangi-Tabrizi, P., Integrating employee timetabling with scheduling of machines and transporters in a job-shop environment: A mathematical formulation and an anarchic society optimization algorithm, Computers & Operations Research, 84, 73-91 (2017) · Zbl 1391.90234 |
| [4] | Akpinar, S.; Elmi, A.; Bektaş, T., Combinatorial benders cuts for assembly line balancing problems with setups, European Journal of Operational Research, 259, 2, 527-537 (2017) · Zbl 1394.90246 |
| [5] | Allahverdi, A., A survey of scheduling problems with no-wait in process, European Journal of Operational Research, 255, 3, 665-686 (2016) · Zbl 1394.90002 |
| [6] | Artigues, C.; Gendreau, M.; Rousseau, L.-M.; Vergnaud, A., Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound, Computers & Operations Research, 36, 8, 2330-2340 (2009) · Zbl 1179.90119 |
| [7] | Benavides, A. J.; Ritt, M.; Miralles, C., Flow shop scheduling with heterogeneous workers, European Journal of Operational Research, 237, 2, 713-720 (2014) · Zbl 1304.90086 |
| [8] | Benders, J. F., Partitioning procedures for solving mixed variables programming problems, Numerische Mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302 |
| [9] | Van den Bergh, J.; Beliën, J.; De Bruecker, P.; Demeulemeester, E.; De Boeck, L., Personnel scheduling: A literature review, European Journal of Operational Research, 226, 3, 367-385 (2013) · Zbl 1292.90001 |
| [10] | Braekers, K.; Hartl, R. F.; Parragh, S. N.; Tricoire, F., A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience, European Journal of Operational Research, 248, 2, 428-443 (2016) · Zbl 1346.90207 |
| [11] | Brucker, P.; Qu, R.; Burke, E., Personnel scheduling: Models and complexity, European Journal of Operational Research, 210, 3, 467-473 (2011) · Zbl 1213.90151 |
| [12] | Canto, S. P., Application of Benders’ decomposition to power plant preventive maintenance scheduling, European Journal of Operational Research, 184, 2, 759-777 (2008) · Zbl 1168.90395 |
| [13] | Chen, J. H.; Lee, D. H.; Cao, J. X., A combinatorial Benders’ cuts algorithm for the quayside operation problem at container terminals, Transportation Research Part E, 48, 1, 266-275 (2012) |
| [14] | Codato, G.; Fischetti, M., Combinatorial Benders’ cuts for mixed-integer linear programming, Operations Research, 54, 4, 756-766 (2006) · Zbl 1167.90601 |
| [15] | De Bruecker, P.; Van den Bergh, J.; Beliën, J.; Demeulemeester, E., Workforce planning incorporating skills: State of the art, European Journal of Operational Research, 243, 1, 1-16 (2015) · Zbl 1346.90470 |
| [16] | Dolgui, A.; Kovalev, S.; Kovalyov, M. Y.; Malyutin, S.; Soukhal, A., Optimal workforce assignment to operations of a paced assembly line, European Journal of Operational Research, 264, 1, 200-211 (2018) · Zbl 1380.90150 |
| [17] | Edis, E. B.; Oguz, C.; Ozkarahan, I., Parallel machine scheduling with additional resources: Notation, classification, models and solution methods, European Journal of Operational Research, 230, 3, 449-463 (2013) · Zbl 1317.90116 |
| [18] | Ernst, A. T.; Jiang, H.; Krishnamoorthy, M.; Sier, D., Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research, 153, 1, 3-27 (2004) · Zbl 1053.90034 |
| [19] | Fischetti, M.; Martello, S.; Toth, P., The fixed job schedule problem with working-time constraints, Operations Research, 37, 3, 395-403 (1989) · Zbl 0672.90074 |
| [20] | Freeman, N. K.; H., M. S.; J., M., A scenario-based approach for operating theater scheduling under uncertainty, Manufacturing & Service Operations Management, 18, 2, 245-261 (2016) |
| [21] | Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman New York · Zbl 0411.68039 |
| [22] | Goel, A., Vehicle scheduling and routing with drivers’ working hours, Transportation Science, 43, 1, 17-26 (2009) |
| [23] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. R., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |
| [24] | Grigoriev, A.; Sviridenko, M.; Uetz, M., Machine scheduling with resource dependent processing times, Mathematical Programming, 110, 1, 209-228 (2007) · Zbl 1192.90073 |
| [25] | Guyon, O.; Lemaire, P.; Pinson, E.; Rivreau, D., Cut generation for an integrated employee timetabling and production scheduling problem, European Journal of Operational Research, 201, 2, 557-567 (2010) · Zbl 1175.90167 |
| [26] | Guyon, O.; Lemaire, P.; Pinson, E.; Rivreau, D., Solving an integrated job-shop problem with human resource constraints, Annals of Operations Research, 213, 1, 147-171 (2014) · Zbl 1296.90046 |
| [27] | Hooker, J. N., Logic-based methods for optimization: Combining optimization and constraint satisfaction (2000), John Wiley and Sons, New York · Zbl 0974.90001 |
| [28] | Hooker, J. N., Planning and scheduling by logic-based Benders decomposition, Operations Research, 55, 3, 588-602 (2007) · Zbl 1167.90512 |
| [29] | Huq, F.; Cutright, K.; Martin, C., Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: A case study, Omega, 32, 2, 121-129 (2004) |
| [30] | Kellerer, H.; Strusevich, V. A., Scheduling parallel dedicated machines under a single non-shared resource, European Journal of Operational Research, 147, 2, 345-364 (2003) · Zbl 1037.90030 |
| [31] | Kellerer, H.; Strusevich, V. A., Scheduling problems for parallel dedicated machines under multiple resource constraints, Discrete Applied Mathematics, 133, 1-3, 45-68 (2004) · Zbl 1053.90039 |
| [32] | Kellerer, H.; Strusevich, V. A., Scheduling parallel dedicated machines with the speeding-up resource, Naval Research Logistics, 55, 5, 377-389 (2008) · Zbl 1209.90174 |
| [33] | Krempels, K.-H.; Panchenko, A., An approach for automated surgery scheduling, Proceedings of the 6th international conference on the practice and theory of automated timetabling, 209-233 (2006) |
| [34] | Lasserre, J.; Queyranne, M., Generic scheduling polyhedral and a new mixed-integer formulation for single-machine scheduling, Proceedings of the 2nd ipco conference, 136-149 (1992) |
| [35] | Lee, S.; McCann, D.; Messenger, J. C., Working time around the world: Trends in working hours, laws, and policies in a global comparative perspective (2007), Routledge |
| [36] | Lodree Jr., E. J.; Geiger, C. D.; Jiang, X., Taxonomy for integrating scheduling theory and human factors: Review and research opportunities, International Journal of Industrial Ergonomics, 39, 1, 39-51 (2009) |
| [37] | Lushchakova, I. N.; Strusevich, V. A., Scheduling incompatible tasks on two machines, European Journal of Operational Research, 200, 2, 334-346 (2010) · Zbl 1177.90174 |
| [38] | Mokotoff, E.; Jimeno, J. L.; Gutiérrez, A. I., List scheduling algorithms to minimize the makespan on identical parallel machines, Top, 9, 2, 243-269 (2001) · Zbl 1024.90043 |
| [39] | Othman, M.; Bhuiyan, N.; Gouw, G. J., Integrating workersdifferences into workforce planning, Computers & Industrial Engineering, 63, 4, 1096-1106 (2012) |
| [40] | Pinedo, M. L., Scheduling: Theory, algorithms, and systems (2016), Springer · Zbl 1332.90002 |
| [41] | Rahmaniani, R.; Crainic, T. G.; Gendreau, M.; Rei, W., The Benders decomposition algorithm: A literature review, European Journal of Operational Research, 259, 3, 801-817 (2017) · Zbl 1402.90158 |
| [42] | Rodrigues, M. M.; de Souza, C. C.; Moura, A. V., Vehicle and crew scheduling for urban bus lines, European Journal of Operational Research, 170, 3, 844-862 (2006) · Zbl 1091.90024 |
| [43] | Saddoune, M.; Desaulniers, G.; Elhallaoui, I.; Soumis, F., Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods, European Journal of Operational Research, 212, 3, 445-454 (2011) · Zbl 1237.90127 |
| [44] | Taşkın, Z. C.; Cevik, M., Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures, Computers & Operations Research, 40, 9, 2178-2186 (2013) · Zbl 1348.90495 |
| [45] | Valls, V.; Pérez, Á.; Quintanilla, S., Skilled workforce scheduling in service centres, European Journal of Operational Research, 193, 3, 791-804 (2009) · Zbl 1180.90141 |
| [46] | Verstichel, J.; Kinable, J.; De Causmaecker, P.; Vanden Berghe, G., A combinatorial Benders’ decomposition for the lock scheduling problem, Computers & Operations Research, 54, 117-128 (2015) · Zbl 1348.90318 |
| [47] | Waersted, M.; Westgaard, R. H., Working hours as a risk factor in the development of musculoskeletal complaints, Ergonomics, 34, 3, 265-276 (1991) |
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.
