On-line integrated production-distribution scheduling problems with capacitated deliveries. (English) Zbl 1177.90122

Summary: In on-line integrated production-distribution problems, customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information about future jobs. Processed jobs are grouped into batches, which are delivered to the customers as single shipments. The total cost (to be minimized) is the sum of the total weighted flow time and the total delivery cost. Such on-line integrated production-distribution problems have been studied for the case of uncapacitated batches. We consider the capacitated case with an upper bound on the size of a batch. For several versions of the problem, we present efficient on-line algorithms, and use competitive analysis to study their worst-case performance.


90B30 Production models
90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
Full Text: DOI


[1] Ahuja, R.; Magnanti, T.; Orlin, J., Network Flows (1993), Prentice Hall: Prentice Hall Upper Saddle River, New Jersey · Zbl 1201.90001
[2] Averbakh, I.; Xue, Z., On-line supply chain scheduling problems with preemption, European Journal of Operational Research, 181, 500-504 (2007) · Zbl 1121.90051
[3] Borodin, A.; El-Yaniv, R., Online Computation and Competitive Analysis (1998), Cambridge University Press · Zbl 0931.68015
[4] Z.-L. Chen, Integrated production and outbound scheduling: Review and extensions, To appear in Operations Research. <http://www.rhsmith.umd.edu/faculty/zchen/chen.htm>; Z.-L. Chen, Integrated production and outbound scheduling: Review and extensions, To appear in Operations Research. <http://www.rhsmith.umd.edu/faculty/zchen/chen.htm>
[5] Chen, Z.-L.; Hall, N., Supply chain scheduling: Conflict and cooperation in assembly systems, Operations Research, 55, 1072-1089 (2007) · Zbl 1167.90504
[6] Chen, Z.-L.; Pundoor, G., Order assignment and scheduling in a supply chain, Operations Research, 54, 555-572 (2006) · Zbl 1167.90505
[7] Chen, Z.-L.; Vairaktarakis, G. L., Integrated scheduling of production and distribution operations, Management Science, 51, 4, 614-628 (2005) · Zbl 1145.90380
[8] Fu, R.; Ji, T.; Yuan, J.; Lin, Y., On-line scheduling in a parallel batch processing system to minimize makespan using restarts, Theoretical Computer Science, 374, 196-202 (2007) · Zbl 1162.90452
[9] Hall, N. G.; Potts, C. N., Supply chain scheduling: Batching and delivery, Operations Research, 51, 4, 566-584 (2003) · Zbl 1165.90455
[10] Hall, N. G.; Potts, C. N., The coordination of scheduling and batch deliveries, Annals of Operations Research, 135, 41-64 (2005) · Zbl 1112.90022
[11] Hoogeveen, J. A.; Vestjens, A. P.A., A best possible on-line algorithm for minimizing maximum delivery time on a single machine, SIAM Journal on Discrete Mathematics, 13, 1, 56-63 (2000) · Zbl 0944.90020
[12] Lee, C.-Y.; Chen, Z.-L., Machine scheduling with transportation considerations, Journal of Scheduling, 4, 3-24 (2001) · Zbl 0979.90055
[13] Poon, C. K.; Yu, W., On-line scheduling algorithms for a batch machine with finite capacity, Journal of Combinatorial Optimization, 9, 167-186 (2005) · Zbl 1079.90060
[14] Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: A review, European Journal of Operational Research, 120, 228-249 (2000) · Zbl 0953.90028
[15] Pruhs, K.; Sgall, J.; Torng, E., On-line scheduling, (Leung, J. Y.-T., Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004), CRC Press), 15.1-15.41, (Chapter 15)
[16] Pundoor, G.; Chen, Z.-L., Scheduling a production-distribution system to optimize the tradeoff between delivery tardiness and total distribution cost, Naval Research Logistics, 52, 571-589 (2005) · Zbl 1122.90358
[17] Seiden, S., Randomized on-line scheduling with delivery times, Journal of Combinatorial Optimization, 3, 399-416 (1999) · Zbl 0958.90048
[18] Tian, J.; Fu, R.; Yuan, J., On-line scheduling with delivery time on a single batch machine, Theoretical Computer Science, 374, 49-57 (2007) · Zbl 1162.90405
[19] van den Akker, M.; Hoogeveen, H.; Vakhania, N., Restarts can help in the on-line minimization of the maximum delivery time on a single machine, Journal of Scheduling, 3, 333-341 (2000) · Zbl 0966.90033
[20] Zhang, G.; Cai, X.; Wong, C. K., On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics, 48, 241-258 (2001) · Zbl 1018.90017
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.