Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

High performance integer optimization for crew scheduling

MPG-Autoren
/persons/resource/persons45344

Sanders,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Sanders, P., Takkula, T., & Wedelin, D. (1999). High performance integer optimization for crew scheduling. In P. Sloot, M. Bubak, A. Hoekstra, & B. Hertzberger (Eds.), Proceedings of the 7th International Conference on High-Performance Computing and Networking Europe (HPCN Europe-99) (pp. 3-12). Berlin: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-35D2-3
Zusammenfassung
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\"oteborg, Sweden, based on distributing the variables and a new sequential \emph{active set strategy} which requires less work and is better adapted to the memory hierachy properties of modern RISC processors. The active set strategy can even be parallelized on networks of workstations.