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

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming computation 2010-12, Vol.2 (3-4), p.259-290
Main Authors: Pessoa, Artur, Uchoa, Eduardo, de Aragão, Marcus Poggi, Rodrigues, Rosiane
Format: Article
Language:English
Subjects:
Full Length Paper
Mathematics
Mathematics and Statistics
Mathematics of Computing
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ||∑ w j T j problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that medium-sized instances of the P ||∑ w j T j have been solved to optimality.
ISSN:1867-2949
1867-2957
DOI:10.1007/s12532-010-0019-z