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

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Artur Pessoa, Eduardo Uchoa, Marcus Poggi de Aragão, Rosiane Rodrigues
DOI:https://doi.org/10.1007/s12532-010-0019-z
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2010
Tag:Software; Theoretical Computer Science
Volume:2
Issue:3-4
Page Number:32
First Page:259
Last Page:290
Mathematical Programming Computation :MPC 2010 - Issue 3-4
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.