G-2004-59
Dantzig-Wolfe Decomposition for Job Shop Scheduling
and BibTeX reference
This article presents a formulation for the job shop problem based on the Dantzig- Wolfe decomposition with a subproblem for each machine. Each subproblem is a sequencing problem on a single machine with time window. The formulation is used within an exact algorithm capable to solve problems with objectives Cmax, Tmax, as well as an objective consistent with the Just-In-Time principle. This objective involves a non-regular cost function of operation completion times. Numerical results are presented for 2 to 10 machine problems involving up to 500 operations.
Published July 2004 , 30 pages
Research Axis
Research application
Publication
Jan 2005
Dantzig-Wolfe decomposition for job shop scheduling
and
Desaulniers, G, Desrosiers, J, Solomon, M, Column Generation, Kluwer Academic Publisher, 271–301, 2005
BibTeX reference