On-line integrated production and outbound distribution scheduling to minimize the maximum delivery completion time. (English) Zbl 1280.68299

Summary: In this paper, we consider the on-line integrated production and outbound distribution scheduling problem to minimize the maximum delivery completion time. All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs are first processed on a single machine and then delivered by a vehicle to a single customer. The vehicle can deliver at most \(c\) jobs to the customer at a time. When preemption is allowed and \(c\geq 2\), we can provide an on-line algorithm with the best competitive ratio \(\frac{\sqrt{5}+1}{2}\approx 1.618\). When preemption is not allowed, we provide an on-line algorithm which has the best competitive ratio \(\frac{\sqrt{5}+1}{2}\approx 1.618\) for the case \(c=1\) and has an asymptotic competitive ratio \(\frac{\sqrt{5}+1}{2}\approx 1.618\) for the case \(c\geq 2\).


68W27 Online algorithms; streaming algorithms
90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
Full Text: DOI


[1] Averbakh, I. (2010). On-line integrated production-distribution scheduling problems with capacitated deliveries. European Journal of Operational Research, 200, 377–384. · Zbl 1177.90122 · doi:10.1016/j.ejor.2008.12.030
[2] Chang, Y.-C., & Lee, C.-Y. (2004). Machine scheduling with job delivery coordination. European Journal of Operational Research, 158, 470–487. · Zbl 1067.90041 · doi:10.1016/S0377-2217(03)00364-3
[3] Chen, Z.-L. (2010). Integrated production and outbound distribution scheduling: review and extensions. Operations Research, 58, 130–148. · Zbl 1233.90151 · doi:10.1287/opre.1080.0688
[4] Chen, Z.-L., & Vairaktarakis, G. L. (2005). Integrated scheduling of production and distribution operations. Management Science, 51, 614–628. · Zbl 1145.90380 · doi:10.1287/mnsc.1040.0325
[5] Hall, N. G., & Potts, C. N. (2003). Supply chain scheduling: batching and delivery. Operations Research, 51, 566–584. · Zbl 1165.90455 · doi:10.1287/opre.51.4.566.16106
[6] Hall, L. A., & Shmoys, D. B. (1992). Johnson’s rule for single-machine scheduling: making a good heuristic better. Mathematics of Operations Research, 17, 22–35. · Zbl 0781.90052 · doi:10.1287/moor.17.1.22
[7] Hoogeveen, J. A., & Vestjen, A. P. A. (2000). A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine. SIAM Journal on Discrete Mathematics, 13, 56–63. · Zbl 0944.90020 · doi:10.1137/S0895480196296823
[8] Lee, C.-Y., &amp; Chen, Z.-L. (2001). Machine scheduling with transportation considerations. Journal of Scheduling, 4, 3–24. · Zbl 0979.90055 · doi:10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO;2-D
[9] Lu, L. F., &amp; Yuan, J. J. (2008a). Unbounded parallel batch scheduling problem with job delivery to minimize makespan. Operations Research Letters, 36, 477–480. · Zbl 1155.90390 · doi:10.1016/j.orl.2008.01.006
[10] Lu, L. F., &amp; Yuan, J. J. (2008b). Single machine scheduling with job delivery to minimize makespan. Asia-Pacific Journal of Operational Research, 25, 1–10. · Zbl 1144.90386 · doi:10.1142/S0217595908001596
[11] Lu, L. F., Yuan, J. J., &amp; Zhang, L. Q. (2008). Single machine scheduling with release dates and job delivery to minimize the makespan. Theoretical Computer Science, 393, 102–108. · Zbl 1136.68016 · doi:10.1016/j.tcs.2007.11.008
[12] Potts, C. N. (1980). Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research, 28, 1436–1441. · Zbl 0447.90041 · doi:10.1287/opre.28.6.1436
[13] Sung, C. S., &amp; Kim, Y. H. (2002). Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed. Computers &amp; Operations Research, 29, 275–294. · Zbl 0993.90051 · doi:10.1016/S0305-0548(00)00071-X
[14] van de Akker, M., Hoogeveen, H., &amp; Vakhania, N. (2000). Restarts can help in the on-line minimization of the maximum delivery time on a single machine. Journal of Scheduling, 3, 333–341. · Zbl 0966.90033 · doi:10.1002/1099-1425(200011/12)3:6<333::AID-JOS53>3.0.CO;2-8
[15] Zhang, G. C., Cai, X. Q., &amp; Wong, C. K. (2001). On-line algorithms for minimizing makespan on batch processing machines. Naval Research Logistics, 48, 241–258. · Zbl 1018.90017 · doi:10.1002/nav.5
[16] Zhang, X. D., &amp; van de Velde, S. (2010). On-line two-machine job shop scheduling with time lags. Information Processing Letters, 110, 510–513. · Zbl 1233.68229 · doi:10.1016/j.ipl.2010.04.002
[17] Zhong, W. Y., Chen, Z.-L., &amp; Chen, M. (2010). Integrated production and distribution scheduling with committed delivery dates. Operations Research Letters, 38, 133–138. · Zbl 1185.90107 · doi:10.1016/j.orl.2009.11.007
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.