PLANET Technology Information Day Prague, May 26, 2003
9:40 - 10:30

Claude Le Pape (ILOG S.A., France)
Constraint-Based Scheduling: Principles and Application

Abstract

Constraint Programming is a problem-solving paradigm which establishes a neat distinction between, on the one hand, a precise definition of the constraints that define the problem to be solved and, on the other hand, the algorithms and heuristics enabling the selection and cancellation of decisions to solve the problem. These principles have been widely applied in the area of scheduling, enabling the implementation of flexible and extensible scheduling systems. Indeed, with Constraint Programming all the specific constraints of a given problem can be represented and actually used as a guide toward a solution. The presentation will provide a non-exhaustive overview of the most widely used Constraint-Based Scheduling techniques, and present an application of Constraint-Based Scheduling to a specific scheduling problem. The problem consists of scheduling batches of molded parts in a three-machine shop according to a wide variety of constraints including machine capabilities, cast-iron availability, minimal and maximal batch sizes, as well as constraints on operation preemption. It illustrates the usefulness of a scheduling library and the importance of its "extensibility", i.e., of the possibility for the user of the library to develop specific types of constraints and specific problem-solving procedures.

Biography

Dr. Claude Le Pape is Director of R&D on Manufacturing Scheduling at ILOG S.A. His main research interests are constraint programming, hybrid problem-solving methods, and their application to complex scheduling problems. He received a PhD in Computer Science from University Paris XI and a Management Degree from "College des Ingénieurs" in 1988. From 1989 to 2001, he was successively postdoctoral student at Stanford University, consultant and software developer at ILOG S.A., senior researcher at BOUYGUES S.A., and research director at BOUYGUES TELECOM, heading a team of 30 researchers in various domains, i.e., telecommunication networks, multimedia technologies, computer science, combinatorial optimization, and social sciences. He designed and developed the first versions of the ILOG SCHEDULER library, as well as CLAIRE SCHEDULE, the first constraint programming library for "preemptive" and "elastic" scheduling. He participated to several European research projects (including the CHIC-2 project on the application of hybrid problem-solving methods to large-scale combinatorial optimization problems) and to the development of many industrial applications in different domains, including mixture design, inventory management, long-term personnel planning, construction site scheduling, and manufacturing scheduling. One of his PhD student, Philippe Baptiste, received both the Robert Faure price from the French Operations Research and Decision Analysis Society (ROADEF) and the Cor Baayen price from the European Research Consortium for Informatics and Mathematics (ERCIM), for his outstanding work at the frontier of operations research and constraint programming.