Mathematical Programming Computation, Volume 2, Numbers 3-4, December 2010

Font Size:  Small  Medium  Large

Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems

Artur Pessoa, Eduardo Uchoa, Marcus Poggi de Aragão, Rosiane Rodrigues


This paper presents an exact algorithm for the identical parallel machine scheduling problem over a formulation where each variable is indexed by a pair of jobs and a completion time.We show that such a formulation can be handled, in spite of its huge number of variables, through a branch cut and price algorithm enhanced by a number of practical techniques, including a dynamic programming procedure to fix variables by Lagrangean bounds and dual stabilization. The resulting method permits the solution of many instances of the P||\sum{wj Tj} problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that medium-sized instances of the P||\sum{wj Tj} have been solved to optimality.

Full Text: PDF

mpc footer
© MPS 2008-2017