An exact algorithm for the preemptive single machine scheduling of equal-length jobs. (English) Zbl 1511.90174
Summary: Many real-world production and service environments can be modeled using the preemptive single machine scheduling problem with equal processing times, arbitrary release dates and weights (priorities) minimizing the total weighted completion time. For this problem we propose a Boolean Linear Programming model, two heuristics based on the model’s relaxation, and an exact Branch and Bound algorithm incorporating the model and heuristics. Our computational study involved more than one million problem instances with up to 350 jobs. Each generated instance has been solved to optimality within 31 min. That improves state-of-the art (at most 20 jobs in 60 min) by more than an order of magnitude. Our benchmark instances and optimal schedules are publicly available at https://data.mendeley.com/datasets/nrkx7467tf/1.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
preemptive scheduling; total weighted completion time; equal processing times; branch and bound; heuristic; benchmarkSoftware:
GurobiReferences:
| [1] | Baptiste, P., Scheduling equal-length jobs on identical parallel machines, Discrete Appl. Math., 103, 1, 21-32 (2000) · Zbl 0971.90027 |
| [2] | Batsyn, M.; Goldengorin, B.; Pardalos, P. M.; Sukhov, P., Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time, Optim. Methods Softw., 29, 955-963 (2014) · Zbl 1299.90131 |
| [3] | Batsyn, M.; Goldengorin, B.; Sukhov, P.; Pardalos, P. M., (Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times. Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times, Springer Proceedings In Mathematics And Statistics, vol. 59 (2013)), 11-27 · Zbl 1344.90020 |
| [4] | Bouma, H. W., All Minimal and Maximal Open Single Machine Scheduling Problems are Pseudo-Polynomially Solvable (2009), Department Of Operations, University Of Groningen, The Netherlands, (Master’s thesis) |
| [5] | Brucker, P.; Knust, S., Complexity results for scheduling problems (2006), URL www.mathematik.uni-osnabrueck.de/research/OR/class/ · Zbl 0946.90026 |
| [6] | Castro, P. M.; Harjunkoski, I.; Grossmann, I. E., Discrete and continuous-time formulations for dealing with break periods: Preemptive and non-preemptive scheduling, Eur. J. Oper. Res., 278, 2, 563-577 (2019) · Zbl 1430.90248 |
| [7] | Epstein, L.; Levin, A., The benefit of preemption for single machine scheduling so as to minimize total weighted completion time, Oper. Res. Lett., 44, 6, 772-774 (2016) · Zbl 1408.90125 |
| [8] | Fomin, A., Goldengorin, B., 2020. [dataset] Benchmark instances for the preemptive single machine scheduling of equal-length jobs minimizing Total Weighted Completion Time (dataset), Mendeley Data. |
| [9] | Gafarov, E.; Werner, F., Two-machine job-shop scheduling with equal processing times on each machine, Mathematics, 301, 1-11 (2019) |
| [10] | Goemans, M. X.; Queyranne, M.; Schulz, A. S.; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM J. Discrete Math., 15, 165-192 (2006) · Zbl 1009.90096 |
| [11] | Goldengorin, B., A correcting algorithm for solving some discrete optimization problems, Dokl. Akad. Nauk SSSR, 270, 3, 525-528 (1983) · Zbl 0555.65042 |
| [12] | Goldengorin, B.; Krushinsky, D., (Linear Assignment Problems in Combinatorial Optimization. Linear Assignment Problems in Combinatorial Optimization, Springer Optimization and Its Applications, vol. 130 (2018)), 183-216 · Zbl 1398.90138 |
| [13] | Graham, R.; Lawler, E.; Lenstra, J.; Kan, A., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discret. Math., 5, 287-326 (1979) · Zbl 0411.90044 |
| [14] | Gurobi Optimization, L., Gurobi optimizer reference manual (2020), URL http://www.gurobi.com |
| [15] | Hendel, Y.; Runge, N.; Sourd, F., The one-machine just-in-time scheduling problem with preemption, Discrete Optim., 6, 10-22 (2009) · Zbl 1159.90020 |
| [16] | Hong, J.; Lee, K.; Pinedo, M. L., Scheduling equal length jobs with eligibility restrictions, Ann. Oper. Res., 285, 295-314 (2020) · Zbl 1429.90023 |
| [17] | Jaramillo, F.; Erkoc, M., Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling, Comput. Ind. Eng., 107, 109-119 (2017) |
| [18] | Jaramillo, F.; Keles, B.; Erkoc, M., Modeling single machine preemptive scheduling problems for computational efficiency, Ann. Oper. Res., 285, 197-222 (2020) · Zbl 1429.90025 |
| [19] | Kagaris, D.; Dutta, S., Scheduling mutual exclusion accesses in equal-length jobs, ACM Trans. Parallel Comput. (2019) |
| [20] | Kravchenko, S. A.; Werner, F., Parallel machine problems with equal processing times: a survey, J. Sched., 14, 435-444 (2011) · Zbl 1280.90058 |
| [21] | Labetoulle, J.; Lawler, E.; Lenstra, J.; Kan., A. R., Preemptive scheduling of uniform machines subject to release dates, (Progress in Combinatorial Optimization (1982)), 245-261 · Zbl 0554.90059 |
| [22] | Lazarev, A. A.; Arkhipov, D. I.; Werner, F., Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan, Optim. Lett., 11, 165-167 (2017) · Zbl 1372.90048 |
| [23] | Lazarev, A. A.; Kvaratskhelia, A. G., Properties of optimal schedules for the minimization total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine, Autom. Remote Control, 71, 2085-2092 (2010) · Zbl 1203.93129 |
| [24] | Lee, K.; Leung, J. Y.T.; Pinedo, M. L., Scheduling jobs with equal processing times subject to machine eligibility constraints, J. Sched., 14, 27-38 (2011) · Zbl 1208.90071 |
| [25] | Romanuke, V., A heuristic’s job order gain in pyramidal preemptive job scheduling problems for total weighted completion time minimization, Inf. Technol. Manag. Sci., 22, 1-8 (2019) |
| [26] | Romanuke, V., Efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions of equal-length jobs, KPI Sci. News, 27-39 (2020) |
| [27] | Schrijver, A., Proving total dual integrality with cross-free families—a general framework, Math. Program., 29, 1, 15-27 (1984) · Zbl 0531.90076 |
| [28] | Schrijver, A., (Theory of linear and integer programming. Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics and Optimization (1999)) |
| [29] | Tanaev, V. S.; Gordon, V. S.; Shafransky, Y. M., Scheduling Theory. Single-Stage Systems (1994), Kluwer academic publishers · Zbl 0827.90079 |
| [30] | Tian, Z.; Ng, C.; Cheng, T., An \(O ( n^2 )\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness, J. Sched., 9, 343-364 (2006) · Zbl 1154.90495 |
| [31] | van den Akker, J. M.; Diepen, G.; Hoogeveen, J. A., Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs, J. Sched., 13, 561-576 (2010) · Zbl 1208.90083 |
| [32] | Wei, H.; Yuan, J., Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time, Oper. Res. Lett., 47, 41-46 (2019) · Zbl 1476.90134 |
| [33] | Xu, Z.; Xu, D., Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time, J. Sched., 21, 461-482 (2018) · Zbl 1406.90049 |
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.
