Groupe d’études et de recherche en analyse des décisions


Dantzig-Wolfe Decomposition for Job Shop Scheduling


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