Resource Constraints for Preemptive Job-shop Scheduling |
| |
Authors: | Claude Le Pape Philippe Baptiste |
| |
Affiliation: | (1) Bouygues, Direction Scientifique, 1, avenue Eugène Freyssinet, 78061 Saint-Quentin-en-Yvelines, France;(2) UMR CNRS 6599 Heudiasyc, Université de Technologie de Compiègne, France |
| |
Abstract: | This paper presents an experimental study of constraint propagation algorithms for preemptive scheduling. We propose generalizations of non-preemptive constraint propagation techniques (based on timetables, on disjunctive constraints, and on edge-finding) to preemptive and mixed problems, i.e., problems in which some activities can be interrupted and some cannot. Another approach relies on incremental flow-based techniques. We theoretically compare these approaches and present an experimental comparison based on a branch and bound procedure for the preemptive variant of the job-shop scheduling problem. We show that both edge-finding and flow-based techniques allow the resolution of hard problem instances, including the preemptive variant of the famous FT10. |
| |
Keywords: | constraint propagation preemptive scheduling resource constraints timetables disjunctive constraints edge-finding network flows job-shop scheduling |
本文献已被 SpringerLink 等数据库收录! |
|