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

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

Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2023 by Zuse Institute Berlin (ZIB).