Special Topics: Scheduling and Planning

Methods and Algorithms

CSC 5811/4811

Spring 2000

Instructor: Professor William J. Wolfe
wwolfe@cse.cudenver.edu
(303) 556-4314 (appointments)
(303) 556-2358 (messages)

Important Notice: April 20, class canceled

Course Overview: This course covers a variety of methods used to solve scheduling and planning problems. The emphasis is on algorithms/heuristics, but there are several system modeling and applications issues that must also be addressed. We begin with some simple scheduling problems, and work our way up to NP-hard problems and the associated heuristics. Along the way we see an evolution of the constraints and objective functions from simple to convoluted. In some examples it seems impossible to provide a quantitative measure of what makes one schedule better than another. At mid semester we will address two real scheduling problems: 1. student scheduling of classes and 2. scheduling "rotations" for medical doctors in training. Planning and schdeuling problems tend to be very difficult because an "optimal" solution usually requires an exhaustive search of all the possible solutions, and the number of possble solutions is usually combinatorially explosive. Thus, for anything but the simplest problems, we are left using "heuristics" that provide "acceptable" solutions most of the time.

Reference Texts: Not Required

  1. Heuristic Scheduling Systems, by Thomas E. Morton, and David W. Pentico.
  2. Introduction to Algorithms, by Cormen, Leiserson, and Rivest.
  3. Intelligent Scheduling, by Monte Zweben.
  4. Artificial Intelligence, by K. Knight and E. Rich.

Concerning Assignments:

  1. All "submitted" assignments are to be posted at a web site. Submit the URL to me by e-mail and I will review the pages etc. If you do not have a web site you must get one (the school offers free hosting for class works, contact the CINS dept. for account information etc)
  2. You must submit your own work, but you can discuss the assignments with anyone.
  3. If you copy anything from anywhere you must put it in quotes and explain where it came from.
  4. All e-mails sent to me must be signed with your full name and course number.

Assignment #1.(Due: Feb 3, 2000) Study the "blocks world planning problem". It is a simple problem that consists of finding the "best" set of moves when moving a set of stacked blocks from one configuration to another. The "moves" that you can make are restricted to:
  1. Pickup: pick up a block off the table (the "hand" must empty before a pickup)
  2. Putdown: put a block (that the hand is holding) down on the table (not on another block)
  3. Stack: put a block (that the hand is holding on top of another block)
  4. Unstack: unstack a block from on top of another block (the block must be "clear")

The problem starts with an initial block configuration, and the task is to find the shortest sequence of of operations (pickup, putdown etc.) that take the blocks to a given goal state.

The problem is defined and analyzed in the Text: Artificial Intelligence by Knight and Rich, but there are also plenty of web sites that deal with this problem (try a search with "artificial intelligence blocks world"). Part of your assignment is to find a web site or two on this topic. I will present the problem in class.

After analyzing the problem, you are to:

  1. submit the best website that you found on this topic.
  2. describe a method that will always find the fewest moves for any pair of initial/goal states. Show an example of how the method works on a case with 5 blocks.
  3. describe a method that will always find a set of moves from intial to goal state, and has the characteristic of being "fast" and easy to understand, but does not always provide the fewest operations. Give an example of where this method does not provide the fewest operations.
  4. think up a way to represent the problem as a "graph theory" problem.

HINT: experiment with several start/goal states for 6 or 7 blocks. Develop a rule for identifying those blocks that must be moved twice (even if we are to have the fewest operations). See example: blocks2.gif

HINT: Great web site! (courtsey of Dennis McDermott -- thanks!):
"On the Complexity of Blocks-World Planning"
(site gives you access to a technical paper that addresses the problem directly).

HINT: Another Great web site! (courtsey of Scott Richard -- thanks!):
"Dave's AI Notes"
(site of AI notes with lots of Blocks World examples and explanations).

HINT: Yet Another Great web site! (courtsey of Craig Chariton -- thanks!):
"Blocks World Tamed"
(refers to a paper on heuristics for the blocks world).

HINT: Yet Another Great web site! (courtsey of John Lindner -- thanks!):
"Blocks World Number of States"
(refers to papers and chat-like sessions/Q&A about blocks world issues --it's a cult!!!).

HINT: Yet Another Great web site! (courtsey of John Lindner -- thanks!):
"Blocks World"
(refers to papers on counting the number of states and heuristics for the blocks world).

HINT: Yet Another Great web site! (courtsey of Clint Stanley -- thanks!):
"TCL SOAR"
(refers to a downloadable blocks world simulator written in TCL-SOAR).

HINT: Yet Another Great web site! (courtsey of David Noi -- thanks!):
"Block World Benchmarks"
(refers to a downloadable blocks world simulator written in TCL-SOAR).

Assignment #2. (Due Feb 10, 2000). Consider the following problem: n jobs that must be done on the same resource, and each job has a fixed start and finish time: {jobi:(si, fi), i = 1, ..., n}. The resource can only handle one job at a time, and jobs cannot be broken into smaller pieces (for future reference, this in know as the "non-preemptive" constraint). Describe an algorithm that will always assign the jobs to the resource so as to get the largest number of jobs done. (Note: the jobs are all of equal value). Also: PROVE that your algorithm is "correct", that it does in fact always provide the maximum number of jobs.

See a simple example at interval_ex.gif

Just as in assignment #1, see if you can create a graph theory representation of the problem.

Assignment #3. (Due Feb 17, 2000). Consider the following problem: n unit length jobs that have due dates and penalties for being late. That is, each job takes exactly one unit of time, and has a due date (di, let this be a positive integer) and a penalty (pi, let this also be a positive integer) that must be paid if the job completes after its due date (the amount of lateness does not matter, there is a single penalty no matter how late the job is). You are to come up with an algorithm that always schedules the jobs so that the total penalty is minimized. Demonstrate your algorithm on a simple case with 7 jobs and random due dates and penalties.
Assignment #4. (Due Feb 24, 2000). Consider the following problem: given a grid of cells with 12 rows and 13 columns, where there are 4 cells randomly chosen in each row that are "off limits". All other cells are available for scheduling. The goal is to schedule at least 4 cells in each row so that:

a. there are no row-adjacent cells scheduled and
b. each column has exactly 4 scheduled cells.

Develop a heuristic that does the scheduling, and quantify its performance by taking a few cases and counting how many times it gave an acceptable solution, and how many times it failed to satisfy the constraints. Also describe the situations where there is no solution that satisfies the constraints.
Assignment #5. (Due Mar 9, 2000). Neighborhood Search. For the TSP (randomly generated cities, (x,y) coordinates in the unit box [0,1]x[0,1]), consider three neighborhood search heuristics. Each of the heuristics starts with a random tour, evaluates all the tours in its neighborhood, and then chooses the best one (if there is no tour that is better than the current tour --> halt). After choosing the best one, evaluate its neighborhood and so on until there is no neighboring tour that is better than the current tour. The three heuristics differ only in the definition of "neighborhood".

The Heurisitics:

1. Swap 2 Cities: this neighborhood is defined as all the tours that can be gotten from the current tour by swapping the position of any 2 cities in the tour. For example, a tour in the neighborhood of the tour <1,2,3,4,5,6,7,8> is <1,2,8,4,5,6,7,3> (cities 3 and 8 were swapped).

2. Arbitrary Insertion: this neighborhood is defined as all the tours that can be gotten from the current tour by taking any city and inserting it between any 2 other cities. For example, a tour in the neighborhood of the tour <1,2,3,4,5,6,7,8> is <1,2,4,5,3,6,7,8> (city 3 was removed from its position and inserted between cities 5 and 6).

3. 2-Opt: this neighborhood is defined as all the tours that can be gotten from the current tour by reversing the order of a subsequence of the tour. For example, one of the tours in the neighborhood of the tour <1,2,3,4,5,6,7,8> is the tour <1,6,5,4,3,2,7,8> (the subsequence 2,3,4,5,6 was reversed).

For you assignment, implement each of these heuristics (any programming language) on 50 randomly generated cities, and compare the results. The "results" should be expressed in a chart: how many trials were run? (should do at least 50 trials). What order did the heuristics perform in? (how many times did heuristics #1, #2, and #3 provide the best tour, the second best tour, the third best tour? Also: explain how you handled "ties" (when at least 2 of the heuristics produce a tour with the same length).
Course Project. (Due May 5, 2000). The recommended project is the "UCD Scheduling Problem", which will be explained in class in great detail. You can, however, submit your own project idea for my approval -- it should involve a large system scheduling problem, but I will approve research projects on Genetic Algorithms and other advanced algorithm ideas etc. In any case, your project report should include a top down design/analysis of a scheduling system, with explanations of: You must also explain how each of the following methods apply, or do not apply, to your problem: Finally, you must explain how multiple criteria effect the Objective function: is there a single measure of "goodness" of the schedule, or are there many measures etc.