Throughput scheduling with equal additive laxity. (English) Zbl 1525.90186
Summary: We study a special case of the classical throughput scheduling problem. The task is to determine a largest set of jobs such that each job \(j\) can complete its processing requirement \(p_j\) within its given time interval \([r_j, d_j)\). In our special case, all jobs have an equal flexibility for starting, referred to as equal additive laxity \(d_j - p_j - r_j = \delta\). We present a polynomial-time algorithm for a single machine and derive approximation algorithms in more general settings.
Keywords:
throughput scheduling; additive laxity; approximation algorithms for scheduling; dynamic programmingReferences:
| [1] | Agnetis, A.; Cosmi, M.; Nicosia, G.; Pacifici, A., An order aggregation and scheduling problem for meal delivery, Optim. Online (2021), Preprint |
| [2] | Auad, R.; Erera, A.; Savelsbergh, M., Using simple integer programs to assess capacity requirements and demand management strategies in meal delivery, Optim. Online (2020), Preprint |
| [3] | Baptiste, P., Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times, J. Sched., 2, 6, 245-252 (1999) · Zbl 0971.90026 |
| [4] | Bar-Noy, A.; Guha, S.; Naor, J.; Schieber, B., Approximating the throughput of multiple machines in real-time scheduling, SIAM J. Comput., 31, 2, 331-352 (2001) · Zbl 0994.68073 |
| [5] | Berman, P.; DasGupta, B., Improvements in throughout maximization for real-time scheduling, (STOC (2000), ACM), 680-687 · Zbl 1296.90040 |
| [6] | Böhm, M.; Megow, N.; Schlöter, J., Throughput scheduling with equal additive laxity, (CIAC. CIAC, Lecture Notes in Comp. Sci., vol. 12701 (2021), Springer), 130-143 · Zbl 07667126 |
| [7] | Chrobak, M.; Dürr, C.; Jawor, W.; Kowalik, L.; Kurowski, M., A note on scheduling equal-length jobs to maximize throughput, J. Sched., 9, 1, 71-73 (2006) · Zbl 1154.90430 |
| [8] | Chuzhoy, J.; Ostrovsky, R.; Rabani, Y., Approximation algorithms for the job interval selection problem and related scheduling problems, Math. Oper. Res., 31, 4, 730-738 (2006) · Zbl 1278.90146 |
| [9] | Cieliebak, M.; Erlebach, T.; Hennecke, F.; Weber, B.; Widmayer, P., Scheduling with release times and deadlines on a minimum number of machines, (Exploring New Frontiers of Theoretical Informatics (2004), Springer), 209-222 · Zbl 1161.68360 |
| [10] | Cosmi, M.; Nicosia, G.; Pacifici, A., Lower bounds for a meal pickup-and-delivery scheduling problem, (17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW) (2019)), 33-36 |
| [11] | Cosmi, M.; Nicosia, G.; Pacifici, A., Scheduling for last-mile meal-delivery processes, IFAC-PapersOnLine, 52, 13, 511-516 (2019) |
| [12] | Cosmi, M.; Oriolo, G.; Piccialli, V.; Ventura, P., Single courier single restaurant meal delivery (without routing), Oper. Res. Lett., 47, 6, 537-541 (2019) · Zbl 1476.90113 |
| [13] | F. Eberle, R. Hoeksma, L. Nölke, B. Simon, Personal communication. |
| [14] | Elffers, J.; de Weerdt, M., Scheduling with two non-unit task lengths is NP-complete (2014), arXiv preprint |
| [15] | Garey, M.; Johnson, D. S.; Simons, B. B.; Tarjan, R. E., Scheduling unit-time tasks with arbitrary release times and deadlines, SIAM J. Comput., 10, 2, 256-269 (1981) · Zbl 0472.68021 |
| [16] | Garey, M. R.; Johnson, D. S., Two-processor scheduling with start-times and deadlines, SIAM J. Comput., 6, 3, 416-426 (1977) · Zbl 0369.90053 |
| [17] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039 |
| [18] | Hyatt-Denesik, D.; Rahgoshay, M.; Salavatipour, M. R., Approximations for throughput maximization (2020), CoRR · Zbl 07765369 |
| [19] | Im, S.; Li, S.; Moseley, B., Breaking 1 - 1/e barrier for non-preemptive throughput maximization, (IPCO. IPCO, Lecture Notes in Comp. Sci., vol. 10328 (2017), Springer), 292-304 · Zbl 1416.90006 |
| [20] | Kise, H.; Ibaraki, T.; Mine, H., A solvable case of the one-machine scheduling problem with ready and due times, Oper. Res., 26, 1, 121-126 (1978) · Zbl 0377.90054 |
| [21] | Reyes, D.; Erera, A.; Savelsbergh, M.; Sahasrabudhe, S.; O’Neil, R., The meal delivery routing problem, Optim. Online (2018) |
| [22] | Sgall, J., Open problems in throughput scheduling, (European Symposium on Algorithms (2012), Springer), 2-11 · Zbl 1365.90148 |
| [23] | Spieksma, F. C., On the approximability of an interval scheduling problem, J. Sched., 2, 5, 215-227 (1999) · Zbl 0938.90034 |
| [24] | Steever, Z.; Karwan, M.; Murray, C., Dynamic courier routing for a food delivery service, Comput. Oper. Res., 107, 173-188 (2019) · Zbl 1458.90142 |
| [25] | Ulmer, M. W.; Thomas, B. W.; Campbell, A. M.; Woyak, N., The restaurant meal delivery problem: dynamic pickup and delivery with deadlines and random ready times, Transp. Sci. (2020) |
| [26] | van Bevern, R.; Niedermeier, R.; Suchỳ, O., A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack, J. Sched., 20, 3, 255-265 (2017) · Zbl 1376.90028 |
| [27] | Yildiz, B.; Savelsbergh, M. W.P., Provably high-quality solutions for the meal delivery routing problem, Transp. Sci., 53, 5, 1372-1388 (2019) |
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.
