Abstract
This chapter presents a formulation for the job shop problem based on Dantzig-Wolfe decomposition with a subproblem for each machine. Each subproblem is a sequencing problem on a single machine with time windows. The formulation is used within an exact algorithm capable of solving problems with objectives C max, T max, as well as an objective consistent with the Just-In-Time principle. This objective involves an irregular cost function of operation completion times. Numerical results are presented for 2 to 10 machine problems involving up to 500 operations.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adams, J., Balas, E., and Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34(3):391–401.
Applegate, D. and Cook, W. (1991). A computational study of the job-shop scheduling problem. Journal on Computing, 3(2):149–157.
Balas, E., Lenstra, J.K., and Vazacopoulos, A. (1995). One machine scheduling with delayed precedence constraints. Management Science, 41(1):94–109.
Barker J.R. and McMahon, G.B. (1985). Scheduling the general job-shop. Management Science, 31(5):594–598.
Blazewicz, J., Domscke, W., and Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 93:1–33.
Brinkkotter, W. and Bruckner, P. (2001). Solving open benchmark instances for the job-shop by parallel head-tail adjustment. Journal of Scheduling, 4(1):53–64.
Brucker, P. and Jurisch, B. (1993). A new lower bound for the job-shop scheduling problem. European Journal of Operational Research, 64:156–167.
Brucker, P., Jurisch, B., and Sievers, B (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49:107–127.
Carlier, J. (1982). The one-machine sequencing problem. European Journal of Operational Research, 11:42–47.
Carlier, J. and Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35(2):164–176.
Carlier, J. and Pinson, E. (1990). A practical use of Jackson’s preemptive schedule for solving the job shop problem. Annals of Operations Research, 26:269–287.
Chen, Z.-L. and Powell W.B. (1999a). A column generation based decomposition algorithm for parallel machine just-in-time scheduling problem. European Journal of Operational Research, 116:220–232.
Chen, Z.-L. and Powell W.B. (1999b). Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing, 11(1):79–94.
Chen, Z.-L. and Powell W.B. (2003). Exact algorithms for scheduling multiple families of jobs on parallel machines. Naval Research Logistics, 50(7):823–840.
Dantzig, G.B. and Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8:101–111.
Desrochers, M., Desrosiers, J., and Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40:342–354.
Dorndorf, V. Pesch, E., and Phan-Huy, T. (2000). Constraint propagation techniques for the disjunctive scheduling problem. Artificial Intelligence, 122(1–2):189–240.
Dorndorf, V. Pesch, E., and Phan-Huy, T. (2002). Constraint propagation and problem decomposition: A preprocessing procedure for the job-shop problem. Annals of Operations Research, 115(1–4):125–145.
Fisher, M.L. (1973). Optimal solution of scheduling problems using Lagrange multipliers—Part 1. Operations Research, 21:1114–1127.
Fisher, M.L., Lageweg, B.J., Lenstra, J.K., and Rinnooy Kan, A.H.G. (1983). Surrogate duality relaxation for job shop scheduling. Discrete Applied Mathematics, 5:65–75.
French, S. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Wiley, New York.
Garey, M.R. and Johnson, D.S. (1979). Computers and Intractability. W.H. Freeman and Co., San Francisco.
Gélinas, S. and Soumis, F. (1997). A dynamic programming algorithm for single machine scheduling with ready times and deadline to minimize total weighted completion time. MIS Collection in the Annals of Operation Research, 69:135–156.
Giffler, B. and Thompson, G.L. (1960). Algorithms for solving production scheduling problems. Operations Research, 8:487–503.
Hoitomt, D.J., Luh, P.B., and Pattipati, K.R. (1993). A practical approach to job-shop scheduling problems. IEEE Transactions on Robotics and Automation, 9(1):1–13.
Join, A.S. and Meeran, S. (1999). Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research, 113(2):390–434.
Lageweg, B.J., Lenstra, J.K., and Rinnooy Kan, A.H.G. (1977). Job-shop scheduling by implicit enumeration. Management Science, 24(4):441–450.
Martin, P. and Shmoys, D.B. (1996). A new approach to computing optimal schedule for the job-shop scheduling problem. Proceedings of the 5th International IPCO conference, pp. 389–403.
McMahon, G. and Florian, M. (1975). On scheduling with ready times and due dates to minimize maximum lateness. Operations Research, 23(3):475–482.
Muth, J.F. and Thompson, G.L. (1963). Industrial Scheduling. Englewood Cliffs, New Jersey. Prentice-Hall.
Rinnooy Kan, A.H.G. (1976). Machine Scheduling Problems: Classification, Complexity and Computations. The Hague, The Netherlands, Martinus Nijhoff, 39.
Roy, B. and Sussman, B. (1964). Les problèmes d’ordonnancement avec contraintes disjonctives. NoteDS No.9 bis, SEMA, Paris.
van den Akker, J.M., Hoogeveen, J.A., and van de Velde, S.L. (1995). Parallel machine scheduling by column generation. Technical Report, Center for Operations Research and Econometrics, Université Catholique de Louvain, Belgium.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer Science+Business Media, Inc.
About this chapter
Cite this chapter
Gélinas, S., Soumis, F. (2005). Dantzig-Wolfe Decomposition for Job Shop Scheduling. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds) Column Generation. Springer, Boston, MA. https://doi.org/10.1007/0-387-25486-2_10
Download citation
DOI: https://doi.org/10.1007/0-387-25486-2_10
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-25485-2
Online ISBN: 978-0-387-25486-9
eBook Packages: Business and EconomicsBusiness and Management (R0)