From manufacturing scheduling to supply chain coordination: The control of complexity and uncertainty

Abstract

With time-based competition and rapid technology advancements, effective manufacturing scheduling and supply chain coordination are critical to quickly respond to changing market conditions. These problems, however, are difficult in view of inherent complexity and various uncertainties involved. Based on a series of results by the authors, decomposition and coordination by using Lagrangian relaxation is identified in this paper as an effective way to control complexity and uncertainty. A manufacturing scheduling problem is first formulated within the job shop context with uncertain order arrivals, processing times, due dates, and part priorities as a separable optimization problem. A solution methodology that combines Lagrangian relaxation, stochastic dynamic programming, and heuristics is developed. Method improvements to effectively solve large problems are also highlighted. To extend manufacturing scheduling within a factory to coordinate autonomic members across chains of suppliers, a decentralized supply chain model is established in the second half of this paper. By relaxing cross-member constraints, the model is decomposed into member-wise subproblems, and a nested optimization structure is developed based on the job shop scheduling results. Coordination is performed through the iterative updating of cross-member prices without accessing other members’ private information or intruding their decision-making authorities, either with or without a coordinator. Two examples are presented to demonstrate the effectiveness of the method. Future prospects to overcome problem inseparability and improve computing efficiency are then discussed.

Keywords

Manufacturing scheduling / supply chain coordination / complexity and uncertainty / decomposition and coordination / Lagrangian relaxation

References

[1] Anupindi R., Bassok Y.. Tayur S., Ganeshan R.. Supply contacts with quantity commitments and stochastic demand. Quantitative Models for Supply Chain Management, 1999, Boston: Kluwer Academic Publishers 198-232.

[2] Arntzen B. C., Brown G. G., Harrison T. P., Trafton L. L.. Global supply chain management at digital equipment corporation. Interface, 1995, 25(1): 69-93.

[3] Bertsekas D. P.. Nonlinear Programming, 1999, Second Edition Belmont, MA: Athena Scientific.

[4] Bertsekas, D. P., Tsitsiklis, J. N., Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, 1989.

[5] Blackstone J. H., Phillips D. T., Hogg G.L.. A State-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research, 1982, 20: 27-45.

[6] Chen F.. Decentralized supply chains subject to information delays. Management Science, 1999, 45(8): 1076-1090.

[7] Chen H., Chu C., Proth J. M.. An Improvement of the lagrangian relaxation approach for job shop scheduling: a dynamic programming method. IEEE Trans. on Robotics and Automation, 1998, 14(5): 786-795.

[8] Chen H. X., Luh P. B., Fang L.. A Time window based approach for job shop scheduling. Proceeding of the 2001 IEEE International Conference on Robotics and Automation, Seoul Korea, 2001, 1: 842-847.

[9] Cohen M. A., Lee H. L.. Strategic analysis of integrated production-distribution systems: models and methods. Operations Research, 1989, 36(2): 216-228.

[10] Custodio L. M. M., Sentieiro J. J. S., Bispo C. F. G.. Production planning and scheduling using a fuzzy decision system. IEEE Transaction on Robotics and Automation, 1994, 10(2): 160-167.

[11] Fisher M. L.. Optimal solution of scheduling problems using lagrange multipliers, Part I. Operation Research, 1973, 21: 1114-1127.

[12] Gaonkar R., Viswanadham N.. Collaboration and information sharing in global contract manufacturing networks. IEEE/ASME Trans. Mechatronics, 2001, 6: 366-376.

[13] Garey M. R., Johnson D. S.. Computers and Intractability, 1979, San Francisco: W. H. Freeman and Co..

[14] Gou L., Luh P. B., Kyoya Y.. Holonic manufacturing scheduling: architecture, cooperation mechanism, and implementation. Computers in Industry, 1998, 37: 213-231.

[15] Guide V. D. R.. Production planning and control for remanufacturing: Industry practice and research needs. Journal of Operations Management, 2000, 18: 467-483.

[16] Kaskavelis C. A., Caramanis M. C.. Efficient lagrangian relaxation algorithms for industry size job-shop scheduling problems. IIE Transactions, 1998, 30(11): 1085-1097.

[17] Kim S. H. A., Cho S.. Variable target value subgradient method. Mathematical Programming, 1991, 49: 359-369.

[18] Kumar P. R., Meyn S. P.. Stability of queuing networks and scheduling policies. IEEE Transaction on Automatic Control, 1995, 40(2): 251-260.

[19] Kuziak A.. Intelligent Manufacturing Systems, 1990, Englewood Cliffs: Prentice-Hall

[20] Lariviere M. A.. Tayur S., Ganeshan R.. Supply chain contracting and coordination with stochastic demand. Quantitative Models for Supply Chain Management, 1999, Boston: Kluwer Academic Publishers 233-268.

[21] Lee H. L., Whang S.. Decentralized multi-echelon supply chains: incentive and information. Management Science, 1999, 45(5): 633-640.

[22] Luh P. B., Chen D., Thakur L. S.. An Effective approach for job-shop scheduling with uncertain processing requirements. IEEE Transactions on Robotics and Automation, 1999, 15(2): 328-339.

[23] Luh P. B., Hoitomt D. J., Max E., Pattipati K. R.. Schedule generation and reconfiguration for parallel machines. IEEE Transactions on Robotics and Automation, 1990, 6(6): 687-696.

[24] Luh P. B., Ni M., Chen H. X., Thakur L. S.. A price-based approach for activity coordination in a supply network. IEEE Transactions on Robotics and Automation, 2003, 18(2): 335-346.

[25] Luh, P. B., Soorapanth, S., Yu, D. Q., and Khibnik, A. I., “Scheduling asset overhaul and repair services,” Proceedings of the 2003 NSF Design, Service and Manufacturing Grantees and Research Conference, Birmingham, AL, pp. 3109–3118, 2003b.

[26] Monahan J. P.. A quantity discount pricing model to increase vendor profits. Management Science, 1984, 30(6): 720-726.

[27] Potts C. N., Van Wassenhove L. N.. Dynamic programming and decomposition approaches for the single machine total tardiness problem. European Journal of Operational Research, 1987, 32: 405-414.

[28] Pinedo M. L.. Scheduling — Theory, Algorithms and Systems, 1995, New Jersey: Prentice Hall.

[29] Smith R. G.. The contract net protocol: high-level communication and control in the distributed problem solver. IEEE Transactions on Computers, 1980, C-29(12): 1104-1113.

[30] Soroush H. M.. Optimal sequence in stochastic single machine shops. Computers and Operations Research, 1996, 23(7): 705-721.

[31] Swaminathan J. M., Smith S. F., Sadeh N. M.. Modeling supply chain dynamics: a multi-agent approach. Decision Sciences, 1998, 29(3): 607-632.

[32] Wang J., Luh P. B., Zhao X.. An optimization-based algorithm for job shop scheduling. SADHANA, 1997, 22: 241-256.

[33] Zhang Y., Luh P. B., Narimatsu K. T., Moriya T. S., Fang L.. A macro-level scheduling method using lagrangian relaxation. IEEE Transactions on Robotics and Automation, 2001, 17(1): 70-79.

[34] Zhao X., Luh P. B., Wang J.. Surrogate gradient algorithms for lagrangian relaxation. Journal of Optimization Theory and Application, 1999, 100(3): 699-712.