Back

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.

, 30 pages

Research Axis

Research application

Publication

Dantzig-Wolfe decomposition for job shop scheduling
and
Desaulniers, G, Desrosiers, J, Solomon, M, Column Generation, Kluwer Academic Publisher, 271–301, 2005 BibTeX reference