TY  - JOUR
U1  - Wissenschaftlicher Artikel
A1  - Pessoa, Artur
A1  - Uchoa, Eduardo
A1  - de Aragão, Marcus Poggi
A1  - Rodrigues, Rosiane
T1  - Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
JF  - Mathematical Programming Computation
N2  - 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.
AB  - 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.
KW  - Software
KW  - Theoretical Computer Science
Y1  - 2010
SN  - 1867-2949
SS  - 1867-2949
U6  - https://doi.org/10.1007/s12532-010-0019-z
DO  - https://doi.org/10.1007/s12532-010-0019-z
VL  - 2
IS  - 3-4
SP  - 259
EP  - 290
S1  - 32
PB  - Springer Science and Business Media LLC
ER  -