The coordination of scheduling and batch deliveries. (English) Zbl 1112.90022
Summary: This paper considers several scheduling problems where deliveries are made in batches with each batch delivered to the customer in a single shipment. Various scheduling costs, which are based on the delivery times of the jobs, are considered. The objective is to minimize the scheduling cost plus the delivery cost, and both single and parallel machine environments are considered. For many combinations of these, we either provide efficient algorithms that minimize total cost or show that the problem is intractable. Our work has implications for the coordination of scheduling with batch delivery decisions to improve customer service.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B30 | Production models |
| 90C39 | Dynamic programming |
References:
| [1] | Albers, S. and P. Brucker. (1993). ”The Complexity of One-Machine Batching Problems.” Discrete Applied Mathematics 47, 87–107. · Zbl 0792.90035 · doi:10.1016/0166-218X(93)90085-3 |
| [2] | Bruno, J. and P. Downey. (1978). ”Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs.” SIAM Journal on Computing 7, 393–404. · Zbl 0386.68050 · doi:10.1137/0207031 |
| [3] | Cheng, T.C.E., V.S. Gordon, and M.Y. Kovalyov. (1996). ”Single Machine Scheduling with Batch Deliveries.” European Journal of Operational Research 94, 277–283. · Zbl 0947.90579 · doi:10.1016/0377-2217(96)00127-0 |
| [4] | Du, J. and J.Y.-T. Leung. (1990). ”Minimizing Total Tardiness on One Machine is NP-Hard.” Mathematics of Operations Research 15, 483–495. · Zbl 0714.90052 · doi:10.1287/moor.15.3.483 |
| [5] | Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman. · Zbl 0411.68039 |
| [6] | Graham, R.L., E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. (1979). ”Optimization and Approximation in Deterministic Machine Scheduling: A Survey.” Annals of Discrete Mathematics 5, 287–326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [7] | Hall, N.G., M.A. Lesaoana, and C.N. Potts. (2001). ”Scheduling with Fixed Delivery Dates.” Operations Research 49, 854–865. · Zbl 1163.90490 · doi:10.1287/opre.49.6.854.10014 |
| [8] | Hall, N.G. and C.N. Potts. (2003). ”Supply Chain Scheduling: Batching and Delivery.” Operations Research 51, 566–584. · Zbl 1165.90455 · doi:10.1287/opre.51.4.566.16106 |
| [9] | Ham, I., K. Hitomi, and T. Yoshida. (1985). Group Technology: Applications to Production Management. Boston, MA: Kluwer-Nijhoff. · Zbl 1179.90108 |
| [10] | Herrmann, J. and C.-Y. Lee. (1993). ”On Scheduling to Minimize Earliness-Tardiness and Batch Delivery Costs with a Common Due Date.” European Journal of Operational Research 70, 272–288. · Zbl 0842.90060 · doi:10.1016/0377-2217(93)90239-J |
| [11] | Karp, R.M. (1972). ”Reducibility among Combinatorial Problems.” In R.E. Miller and J.W. Thatcher (eds.), Complexity of Computer Computations. New York: Plenum Press, pp. 85–103. |
| [12] | Kruse, R.L. (1987). Data Structures and Program Design, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall. |
| [13] | Lawler, E.L. (1977). ”A ’Pseudopolynomial’ Time Algorithm for Sequencing Jobs to Minimize Total Tardiness.” Annals of Discrete Mathematics 1, 331–342. · Zbl 0353.68071 · doi:10.1016/S0167-5060(08)70742-8 |
| [14] | Lee, C.-Y. and Z.-L. Chen. (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 |
| [15] | Lee, C.-Y., R. Uzsoy, and L.A. Martin-Vega. (1992). ”Efficient Algorithms for Scheduling Semiconductor Burn-in Operations.” Operations Research 40, 764–775. · Zbl 0759.90046 · doi:10.1287/opre.40.4.764 |
| [16] | Lenstra, J.K., A.H.G. Rinnooy Kan, and P. Brucker. (1977). ”Complexity of Machine Scheduling Problems.” Annals of Discrete Mathematics 1, 343–362. · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X |
| [17] | Monma, C.L. and C.N. Potts. (1989). ”On the Complexity of Scheduling with Batch Setup Times.” Operations Research 37, 798–804. · Zbl 0686.90025 · doi:10.1287/opre.37.5.798 |
| [18] | Moore, J.M. (1968). ”An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs.” Management Science 15, 102–109. · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102 |
| [19] | Potts, C.N. and M.Y. Kovalyov. (2000). ”Scheduling with Batching: A Review.” European Journal of Operational Research 120, 228–249. · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8 |
| [20] | Potts, C.N. and L.N. Van Wassenhove. (1992). ”Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity.” Journal of the Operational Research Society 43, 395–406. · Zbl 0756.90050 |
| [21] | Webster, S. and K.R. Baker. (1995). ”Scheduling Groups of Jobs on a Single Machine.” Operations Research 43, 692–703. · Zbl 0857.90062 · doi:10.1287/opre.43.4.692 |
| [22] | Yang, X. (2000). ”Scheduling with Generalized Batch Delivery Dates and Earliness Penalties.” IIE Transactions 32, 735–742. |
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.
