Abstract
Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. Because of the combinatorial nature of scheduling problems, it is often difficult to find optimal schedules, especially within a limited amount of computation time. Production schedules therefore are usually generated by using heuristics in practice. However, it is very difficult to evaluate the quality of these schedules, and the consistency of performance may also be an issue.
In this paper, near-optimal solution methodologies for job shop scheduling are examined. The problem is formulated as integer optimization with a “separable” structure. The requirement of on-time delivery and low work-in-process inventory is modelled as a goal to minimize a weighted part tardiness and earliness penalty function. Lagrangian relaxation is used to decompose the problem into individual part subproblems with intuitive appeal. By iteratively solving these subproblems and updating the Lagrangian multipliers at the high level, near-optimal schedules are obtained with a lower bound provided as a byproduct. This paper reviews a few selected methods for solving subproblems and for updating multipliers. Based on the insights obtained, a new algorithm is presented that combines backward dynamic programming for solving low level subproblems and interleaved conjugate gradient method for solving the high level problem. The new method significantly improves algorithm convergence and solution quality. Numerical testing shows that the method is practical for job shop scheduling in industries.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adams J, Balas E, Zawack D 1988 The shifting bottleneck procedure for job shop scheduling.Manage. Sci. 34: 391–401
Baker K 1974Introduction to sequencing and scheduling (New York: Wiley)
Bertsekas D P 1995Nonlinear programming (Belmont, MA: Athena Scientific)
Blackstone J H, Phillips D T, Hogg G L 1982 A state-of-the-art survey of dispatching rules for manufacturing job shop operations.Int. J. Product. Res. 20: 27–45
Chen H, Chu C, Proth J M 1995 A more efficient Lagrangian relaxation approach to job-shop scheduling problems.Proc. IEEE Int. Conf. on Robotics and Automation, pp 496–501
Czerwinski C, Luh P B 1994 Scheduling parts with bills of materials using an improved Lagrangian relaxation technique.IEEE Trans. Robotics Autom. 10: 99–111
Fisher M L 1973 Optimal solution of scheduling problems using Lagrange multipliers. Part I.Oper. Res. 21: 1114–1127
Garey M R, Johnson D S 1979Computers and intractability (San Francisco: WH Freeman)
Hiriart-Urruty J B, Lemarechal C 1993Convex analysis and minimization algorithms (Berlin: Springer-Verlag) vols 1 & 2
Kaskavelis C A, Caramanis M C 1995 Efficient Lagrangian relaxation algorithms for real-life-size job-shop scheduling problems. Working Paper, Department of Manufacturing Engineering, Boston University; also personal communications
Kuziak A 1990Intelligent manufacturing systems (Englewood Cliffs, NJ: Prentice-Hall)
Luh P B, Hoitomt D J 1993 Scheduling of manufacturing systems using the Lagrangian relaxation technique.IEEE Trans. Autom. Control. 38: 1066–1079
Luh P B, Gou L, Odahara T, Tsuji M, Yoneda K, Hasegawa T, Kyoya Y 1995 Job shop scheduling with group-dependent setups, finite buffers, and long time horizon.Proceedings of the 34th Conference on Decision and Control, New Orleans, LA, pp 4184–4189
Luh P B, Chen D, Thakur L S 1997a Modelling uncertainty in job shop scheduling.Proc. of the First International Conference on Operations and Quantitative Management, Jaipur, India, pp 490–497
Luh P B, Wang J H, Wang J L, Tomastik R N 1997b Near optimal scheduling of manufacturing systems with presence of batch machines and setup requirements.Ann. CIRP 46: (to appear)
Pinedo M 1995Scheduling — Theory, algorithms and systems (Englewood Cliffs, NJ: Prentice Hall)
Tomastik R N, Luh P B 1993 The facet ascending algorithm for integer programming problems.Proc. IEEE Conf. on Decision and Control, San Antonio, Texas, pp 2880–2884
Tomastik R N, Luh P B 1996 A reduced-complexity bundle method for maximizing concave non-smooth functions.Proc. of the 31st Conference on Decision and Control, Kobe, Japan, pp 2114–2119
Ventura J A, Weng M X 1995 Minimizing single-machine completion time variance.Manage. Sci. 41: 1448–1455
Author information
Authors and Affiliations
Additional information
This work was supported in part by the National Science Foundation under DMI-9500037, and the Advanced Technology Center for Precision Manufacturing, University of Connecticut.
Rights and permissions
About this article
Cite this article
Wang, J., Luh, P.B., Zhao, X. et al. An optimization-based algorithm for job shop scheduling. Sadhana 22, 241–256 (1997). https://doi.org/10.1007/BF02744491
Issue Date:
DOI: https://doi.org/10.1007/BF02744491