Incorporating the strength of MIP modeling in schedule construction

Cor A.J. Hurkens

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 4, page 409-420
  • ISSN: 0399-0559

Abstract

top
Linear programming techniques can be used in constructing schedules but their application is not trivial. This in particular holds true if a trade-off has to be made between computation time and solution quality. However, it turns out that – when handled with care – mixed integer linear programs may provide effective tools. This is demonstrated in the successful approach to the benchmark constructed for the 2007 ROADEF computation challenge on scheduling problems furnished by France Telecom.

How to cite

top

Hurkens, Cor A.J.. "Incorporating the strength of MIP modeling in schedule construction." RAIRO - Operations Research 43.4 (2009): 409-420. <http://eudml.org/doc/250646>.

@article{Hurkens2009,
abstract = { Linear programming techniques can be used in constructing schedules but their application is not trivial. This in particular holds true if a trade-off has to be made between computation time and solution quality. However, it turns out that – when handled with care – mixed integer linear programs may provide effective tools. This is demonstrated in the successful approach to the benchmark constructed for the 2007 ROADEF computation challenge on scheduling problems furnished by France Telecom. },
author = {Hurkens, Cor A.J.},
journal = {RAIRO - Operations Research},
keywords = {Scheduling; integer programming; lower bounds; hybrid methods. ; scheduling; hybrid methods},
language = {eng},
month = {10},
number = {4},
pages = {409-420},
publisher = {EDP Sciences},
title = {Incorporating the strength of MIP modeling in schedule construction},
url = {http://eudml.org/doc/250646},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Hurkens, Cor A.J.
TI - Incorporating the strength of MIP modeling in schedule construction
JO - RAIRO - Operations Research
DA - 2009/10//
PB - EDP Sciences
VL - 43
IS - 4
SP - 409
EP - 420
AB - Linear programming techniques can be used in constructing schedules but their application is not trivial. This in particular holds true if a trade-off has to be made between computation time and solution quality. However, it turns out that – when handled with care – mixed integer linear programs may provide effective tools. This is demonstrated in the successful approach to the benchmark constructed for the 2007 ROADEF computation challenge on scheduling problems furnished by France Telecom.
LA - eng
KW - Scheduling; integer programming; lower bounds; hybrid methods. ; scheduling; hybrid methods
UR - http://eudml.org/doc/250646
ER -

References

top
  1. D. Applegate and W. Cook, A computational study of the job-shop scheduling problem. ORSA J. Comput.3 (1991) 149–156.  Zbl0755.90039
  2. E.L. Lawler and J. Labetoulle, On preemptive scheduling of unrelated parallel processors by linear programming. J. Assoc. Comput. Mach.25 (1978) 612–619.  Zbl0388.68027
  3. Y. Pochet and Laurence A. Wolsey, Production planning by mixed integer programming. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006) xxiv+499 p.  Zbl1102.90039

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.