Parallel integer optimization for crew scheduling

Parallel integer optimization for crew scheduling

0.00 Avg rating0 Votes
Article ID: iaor2002437
Country: Netherlands
Volume: 99
Issue: 1
Start Page Number: 141
End Page Number: 166
Publication Date: Dec 2000
Journal: Annals of Operations Research
Authors: , , ,
Keywords: vehicle routing & scheduling, personnel & manpower planning
Abstract:

Performance aspects of a Lagrangian relaxation based heuristic for solving large 0–1 integer linear programs are discussed. In particular, we look at its application to airline and railway crew scheduling problems. We present a scalable parallelization of the original algorithm used in production at Carmen Systems AB, Göteborg, Sweden, based on distributing the variables. A lazy variant of this approach which decouples communication and computation is even useful on networks of workstations. Furthermore, we develop a new sequential active set strategy which requires less work and is better adapted to the memory hierarchy properties of modern RISC processors. This algorithm is also suited for parallelization on a moderate number of networked workstations.

Reviews

Required fields are marked *. Your email address will not be published.