Solving scheduling problems from high-level models
(2010)
Files
thesis-monette.pdf
Open Access - Adobe PDF
- 1.6 MB
Details
- Authors
- Supervisors
- Abstract
- (en) Scheduling consists in deciding when a set of activities must be executed under different constraints, in order to optimize a given objective. The two main types of constraints are precedences between activities, and the availability of finite resources. Common objectives are to minimize the total duration, or to minimize the weighted sum of the tardiness of activities with respect to given due-dates. Scheduling problems are very varied, both in application domains and in featured constraints. They have been a large area of research for decades. A lot of work has been undertaken to express, classify, and solve scheduling problems. Most of these problems are computationally hard to solve (in the sense of being NP-complete) and need complex algorithms (using techniques in the domains of Operations Research and Artificial Intelligence, such as e.g. Constraint Programming, Local and Heuristic Search, Mathematical Programming). But the difficulty lies also in the modeling of the problems, and the mapping between high-level, declarative models and low-level, procedural search techniques. The problem we are tackling is the gap between the high-level modeling of scheduling problems and their efficient resolution. This gap has several causes. First, most search techniques deal with more or less pure problems, and may not be easily adapted to solve problems with side constraints. Second, it requires a strong background in operations research to cast the problem to the right representation. Our goal is to facilitate the work of the user, such that no particular expertise is needed to solve a problem of scheduling. Our contributions in this direction are listed next: * Strong separation between modeling and solving. * Structural analysis and classification of problems. * Synthesis techniques to automatically generate search algorithms for a model. * Simple combination of several search algorithms, to create loosely coupled hybrid algorithms (in particular using Constraint Programming and Local Search). As a proof of concept, we developed a system, Aeon, supporting the above contributions. It provides a high-level modeling library for scheduling problems and a set of solvers for such problems. A user can model his/her problem in Aeon, and solve it with different search algorithms, without having to write the search procedure. Experimental results show the time spent to analyze a model and to generate an appropriate algorithm is very low. Furthermore, the generated searches give similar results to algorithms written directly in the Comet Solver, on which Aeon is based. Additionally, our thesis introduces new results on deduction techniques in Constraint Programming. In particular, we present two propagators of global constraints for scheduling problems. The first one is based on the positions of activities to propagate the disjunctive resource constraints. The second one propagates the minimization of the sum over all activities of the earliness and tardiness costs (a so-called Just-In-Time objective function). Using this second propagator, we were able to improve several best known solutions on a hard benchmark of Just-In-Time Scheduling.
- Affiliations
Citations
Monette, J.-N. (2010). Solving scheduling problems from high-level models. https://hdl.handle.net/2078.5/130211