Logistics scheduling: Analysis of two-stage problems

Abstract

This paper studies the coordination effects between stages for scheduling problems where decision-making is a two-stage process. Two stages are considered as one system. The system can be a supply chain that links two stages, one stage representing a manufacturer; and the other, a distributor. It also can represent a single manufacturer, while each stage represents a different department responsible for a part of operations. A problem that jointly considers both stages in order to achieve ideal overall system performance is defined as a system problem. In practice, at times, it might not be feasible for the two stages to make coordinated decisions due to (i) the lack of channels that allow decision makers at the two stages to cooperate, and/or (ii) the optimal solution to the system problem is too difficult (or costly) to achieve.

Two practical approaches are applied to solve a variant of two-stage logistic scheduling problems. The Forward Approach is defined as a solution procedure by which the first stage of the system problem is solved first, followed by the second stage. Similarly, the Backward Approach is defined as a solution procedure by which the second stage of the system problem is solved prior to solving the first stage. In each approach, two stages are solved sequentially and the solution generated is treated as a heuristic solution with respect to the corresponding system problem. When decision makers at two stages make decisions locally without considering consequences to the entire system, ineffectiveness may result — even when each stage optimally solves its own problem. The trade-off between the time complexity and the solution quality is the main concern. This paper provides the worst-case performance analysis for each approach.

Keywords

Logistics scheduling / worst case analysis / dynamic programming

References

[1] Ahmadi J. H., Ahmadi R. H., Dasu S., Tang C. S.. Batching and scheduling jobs on batch and discrete processors. Operations Research, 1992, 39: 750-763.

[2] Chang, Y.-C., C.-Y. Lee, “Machine scheduling with job delivery coordination”, To appear in European Journal of Operational Research, 2002.

[3] Chen Z.-L.. Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs. European Journal of Operational Research, 1996, 93: 49-60.

[4] Cheng T.C.E., Gordon V. S., Kovalyov M. Y.. Single machine scheduling with batch deliveries. European Journal of Operational Research, 1996, 94: 277-283.

[5] Conway R. W., Maxwell W. L., Miller L. W.. Theory of Scheduling, 1967, Reading, MA: Addison-Wesley.

[6] Garey M.R., Johnson D. S., Sethi R.. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1976, 1: 117-129.

[7] Gonzalez T., Sahni S.. Flowshop and jobshop schedules: complexity and approximation. Operations Research, 1978, 26: 36-52.

[8] Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G.. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 1979, 5: 287-326.

[9] Hall N. G., Lesaoana M. A., Potts C. N.. Scheduling with fixed delivery dates. Operations Research, 2001, 49: 134-144.

[10] Hall N. G., Potts C. N.. Supply chain scheduling: batching and delivery. Operations Research, 2003, 51: 566-584.

[11] Herrmann J. W., Lee C.-Y.. On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date. European Journal of Operational Research, 1993, 70: 272-288.

[12] Hoogeveen J. A., Kawaguchi T.. Minimizing total completion time in a two-machine flowshop: analysis of special cases. Mathematics of Operations Research, 1999, 24: 887-910.

[13] Hurink J., Knust S.. Makespan minimization for flow-shop problems with transportation times. Discrete Applied Mathematics, 2001, 112: 199-216.

[14] Ignall E., Schrage L.. Application of the branch and bound technique for some flow-shop scheduling problems. Operations Research, 1965, 13: 400-412.

[15] Jackson J. R.. Scheduling a production line to minimize maximum tardiness. Research report 43. Management Science Research Project, 1955, Los Angeles, CA: University of California

[16] Johnson S. M.. Optimal two-and three-stage production schedules with setup times included. Naval Research Logistic Quarterly, 1954, 1: 61-68.

[17] Lee C.-Y., Chen Z.-L.. Machine scheduling with transportation considerations. Journal of Scheduling, 2001, 4: 3-24.

[18] Lenstra J. K., Rinnooy Kan A. H. G., Brucker P.. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1977, 1: 343-362.

[19] Potts C. N., Kovalyov M. Y.. Scheduling with batching: a review. European Journal of Operational Research, 2000, 120: 228-249.

[20] Potts C. N., Van Wassenhove L. N.. Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity. Journal of the Operational Research Society, 1992, 43: 395-406.

[21] Sarmiento A. M., Nagi R.. A review of integrated analysis of production-distribution systems. IIE Transactions, 1999, 31: 1061-1074.

[22] Schrage L. E.. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 1968, 16: 687-690.

[23] Smith W. E.. Various Optimizers for Single-stage Production. Naval Research Logistics Quarterly, 1956, 3: 59-66.

[24] Thomas D. J., Griffin P. M.. Coordinated supply chain management. European Journal of Operational Research, 1996, 94: 1-15.

[25] Webster S., Baker K. R.. Scheduling groups of jobs on a single machine. Operations Research, 1995, 43: 692-703.

[26] Van de Velde S. L.. Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation. Annals of Operations Research, 1990, 26: 257-268.

[27] Yang X.. Scheduling with generalized batch delivery dates and earliness penalties. IIE Transactions, 2000, 32: 735-741.

[28] Yuan J.. A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs. European Journal of Operational Research, 1996, 94: 203-205.