Optimization Online


Algorithms over Arc-time Indexed Formulations for Single and Parallel Machine Scheduling Problems

Artur Pessoa (artur***at***producao.uff.br)
Eduardo Uchoa (uchoa***at***producao.uff.br)
Marcus Poggi de Arag„o (poggi***at***inf.puc-rio.br)
Rosiane Rodrigues (rosiane***at***cos.ufrj.br)

Abstract: This paper presents algorithms for single and parallel identical machine scheduling problems. While the overall algorithm can be viewed as a branch-cut-and-price over a very large extended formulation, a number of auxiliary techniques are necessary to make the column generation effective. Those techniques include a powerful fixing by reduced costs and a new proposed dual stabilization method. We tested the algorithms on instances of the classical weighted tardiness problem. All the 375 single machine instances from the OR-Library, with up to 100 jobs, are solved to optimality in reasonable computational times and with minimal branching, since the duality gaps are almost always reduced to zero in the root node. Many multi-machine instances with 40 and 50 jobs are also solved to optimality for the first time. The proposed algorithms and techniques are quite generic and can be used on several related scheduling problems.

Keywords: scheduling, column generation, cut generation, formulations

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Integer Programming

Citation: Report RPEP Universidade Federal Fluminense Vol. 8 no. 8

Download: [PDF]

Entry Submitted: 06/25/2008
Entry Accepted: 06/25/2008
Entry Last Modified: 06/26/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society