Scheduling
Scheduling is the problem of assigning a set of tasks to a
set of resources subject to a set of constraints. Examples of
scheduling constraints include deadlines (e.g., job i must be completed
by time t), resource capacities (e.g., there are only four drills),
precedence constraints on the order of tasks (e.g., a piece must be
sanded before it is painted), and priorities on tasks (e.g., finish
job j as soon as possible while meeting the other deadlines).
Examples of scheduling domains include classical job-shop scheduling,
manufacturing scheduling, and transportation scheduling.
CIRL
CIRL has used a variety of techniques to solve scheduling problems.
Recent work has made use of nonsystematic techniques such as
squeaky wheel optimization and schedule packing (also known as
doubleback optimization) to solve problems that arise in manufacturing
scheduling. Other work has combined systematic and nonsystematic
techniques, such as limited discrepancy search (LDS) with schedule packing,
and squeaky wheel with Operations Research methods.
Pointers
-
Squeaky Wheel Optimization.
- An article by David Joslin and Dave Clements describing squeaky wheel
and how it was applied to scheduling work in a fiber optic
cable assembly plant, and to a standard set of graph coloring problems.
Appeared in Journal of Artificial Intelligence Research, May 1999.
A
conference version of this material appeared in
Proc. AAAI in 1998.
Compressed postscript.
-
Cyclic Scheduling.
- This paper by Denise Draper, Ari Jonsson,
Dave Clements, and David Joslin describes a constraint based approach
to cyclical scheduling problems. Appeared in
Proceedings of the 16th International Joint
Conference on Artificial Intelligence (IJCAI-99).
-
Heuristic Optimization: A Hybrid AI/OR Approach.
- This article describes a combined AI and Operations Research (OR)
effort on scheduling problems that produces better solutions than did
AI or OR techniques on their own.
This was joint work between CIRL and George Nemhauser, Markus Puttlitz,
and Martin Savelsbergh at Georgia Tech.
Presented at the Workshop on Industrial Constraint-Directed
Scheduling, held in conjunction with Proc. CP in 1997.
Compressed postscript.
-
An Approach to Resource Constrained Project Scheduling
-
This paper by James Crawford gives an overview of an approach to Resource
Constrained Project Scheduling (RCPS) problems. The approach is based on the
combination of schedule packing (referred to as doubleback optimization
in this paper) with LDS,
and generated the best known solutions to benchmark
problems of realistic size and character. It
appeared in the 1996 Artificial Intelligence and Manufacturing
Research Planning Workshop. Postscript.
-
Limited Discrepancy Search
- Article introducing limited discrepancy search, developed
by Will Harvey and Matt Ginsberg. Appeared in Proc. IJCAI
in 1995. Compressed postscript.
-
Experimental Results on the Application of Satisfiability
Algorithms to Scheduling Problems
- Article by Andrew Baker and James Crawford, reporting the
results of running various solvers on a well known suite of scheduling
problems. Appeared in Proc. AAAI in 1994. Compressed postscript.
- Application program:
- Aircraft assembly
- Cable manufacturing
- Parent areas:
- Problem Domains
Back to the CIRL Overview Page.