Just-In-Time Scheduling with Constraint Programming

Monette, Jean-Noël;Deville, Yves;Van Hentenryck, Pascal
(2009) International conference on automated planning and scheduling (ICAPS) — Location: Tessaloniki, Greece (2009)

Files

just-in-time.pdf
  • Open Access
  • Adobe PDF
  • 279.3 KB
Download

Details

Authors
  • Monette, Jean-NoëlUCLouvain
    Author
  • Deville, Yvesorcid-logoUCLouvain
    Author
  • Van Hentenryck, PascalBrown University, USA
    Author
Abstract
This paper considers Just-In-Time Job-Shop Scheduling, in which each activity has an earliness and a tardiness cost with respect to a due date. It proposes a constraint programming approach, which includes a novel filtering algorithm and dedicated heuristics. The filtering algorithm uses a machine relaxation to produce a lower bound that can be obtained by solving a Just-In-Time Pert problem. It also includes pruning rules which update the variable bounds and detect precedence constraints. The paper presents experimental results which demonstrate the effectiveness of the approach over a wide range of benchmarks.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Monette, J.-N., Deville, Y., & Van Hentenryck, P. (2009). Just-In-Time Scheduling with Constraint Programming. International conference on automated planning and scheduling (ICAPS), Tessaloniki, Greece. https://hdl.handle.net/2078.5/253683