Logistics scheduling with batching and transportation. (English) Zbl 1146.90027

Summary: This paper studies a general two-stage scheduling problem, in which jobs of different importance are processed by one first-stage processor and then, in the second stage, the completed jobs need to be batch delivered to various pre-specified destinations in one of a number of available transportation modes. Our objective is to minimize the sum of weighted job delivery time and total transportation cost. Since this problem involves not only the traditional performance measurement, such as weighted completion time, but also transportation arrangement and cost, key factors in logistics management, we thus call this problem logistics scheduling with batching and transportation (LSBT) problem.We draw an overall picture of the problem complexity for various cases of problem parameters accompanied by polynomial algorithms for solvable cases. On the other hand, we provide for the most general case an approximation algorithm of performance guarantee.


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


[1] Albers, S.; Brucker, P., The complexity of one-machine batching problems, Discrete applied mathematics, 47, 107-877, (1993) · Zbl 0792.90035
[2] Blazewicz, J.; Ecker, K.; Schmidt, G.; Weglarz, J., Scheduling computer and manufacturing processes, (2001), Springer-Verlag Berlin · Zbl 0985.90033
[3] Brucker, P., Scheduling algorithms, (2001), Springer-Verlag Berlin · Zbl 1051.90011
[4] Chen, Z.-L., Scheduling and common due date assignment with earliness – tardiness penalties and batch delivery costs, European journal of operational research, 93, 49-60, (1996) · Zbl 0916.90147
[5] Chen, Z.-L.; Vairaktarakis, G.L., Integrated scheduling of production and distribution operations, Management science, 51, 614-628, (2005) · Zbl 1145.90380
[6] Cheng, T.C.E.; Gordon, V.S.; Kovalyov, M.Y., Single machine scheduling with batch deliveries, European journal of operational research, 94, 277-283, (1996) · Zbl 0947.90579
[7] Hall, N.G.; Lesaoana, M.A.; Potts, C.N., Scheduling with fixed delivery dates, Operations research, 49, 134-144, (2001) · Zbl 1163.90459
[8] Hall, N.G.; Potts, C.N., Supply chain scheduling: batching and delivery, Operations research, 51, 566-584, (2003) · Zbl 1165.90455
[9] Herrmann, J.; Lee, C.-Y., On scheduling to minimize earliness – tardiness and batch delivery costs with a common due date, European journal of operational research, 70, 272-288, (1993) · Zbl 0842.90060
[10] Lee, C.-Y.; Chen, Z.-L., Machine scheduling with transportation considerations, Journal of scheduling, 4, 3-24, (2001) · Zbl 0979.90055
[11] Li, C.-L.; Vairaktarakis, G.; Lee, C.-Y., Machine scheduling with deliveries to multiple customer locations, European journal of operational research, 164, 39-51, (2005) · Zbl 1132.90329
[12] Matsuo, H., The weighted total tardiness problem with fixed shipping times and overtime utilization, Operations research, 36, 293-307, (1988) · Zbl 0655.90037
[13] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1998), Dover Publications · Zbl 0944.90066
[14] Pinedo, M., Scheduling: theory, algorithms, and systems, (2002), Prentice Hall Englewood Cliffs, New Jersey · Zbl 1145.90394
[15] Soukhal, A.; Oulamara, A.; Martineau, P., Complexity of flow shop scheduling problems with transportation constraints, European journal of operational research, 161, 32-41, (2005) · Zbl 1065.90043
[16] H. Wang, C.-Y. Lee, Two-stage logistics scheduling with two-mode transportation, To appear in Naval Research Logistics.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.