You are here

Just-In-Time Scheduling With Constraint Programming

TitleJust-In-Time Scheduling With Constraint Programming
Publication TypeConference Proceedings
Year of Conference2009
AuthorsMonette, Jean-Noël, Deville Yves, and Van Hentenryck Pascal
Conference Name19th International Conference on Automated Planning and Scheduling (ICAPS 2009)
Date Published19/09/2009
Conference LocationTessaloniki, Greece

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.