NOTES ON SCHEDULING AND ITERATIVE REPAIR Notes by Jim Neudorf (these summarize Jim's presentation). There are a number of scheduling problems and an associated number of heuristics to solve them. These notes contain a few of the more fundamental scheduling problems. These problems, since they are scheduling problems, can be represented as constraint satisfaction problems. Iterative repair, as used in the Gerry task scheduling program, considers constraints on resources and state variables to schedule tasks for completion. Gerry uses the Waltz algorithm to maintain task ordering within a job and tries to avoid local minimums by employing simulated annealing. BASIC SCHEDULING PROBLEMS * N-job, M-machine problem (All jobs consist of only 1 task) __ __ __ BDEAC -----> |__| ------> |__| ------> |__| -------> For this problem all jobs must visit all machines. Jobs visit all machines in the same order. The first job in the order is the first job to finish. The last job in the order is the last job to finish all machines. * Flow Line For this problem each item has a number of tasks that are needed. Certain tasks may be completed by certain stations on the line. The goal is to consider the rate at which items enter the line and to schedule the different items so that no work station is overloaded. * Resource Allocation In resource allocation jobs contain 1 to k tasks which are completed by particular resources. Tasks for a job have an established order. The goal is to schedule the tasks of N jobs on the resources so that no resource is performing 2 tasks at the same time. CONSTRAINT SATISFACTION PROBLEM REPRESENTATION * Constraint satisfaction problem Scheduling problems are typically represented in terms of a set of variables and constraints on their values. A schedule is then represented as an assignment of values to all of the variables that satisfies all the constraints. The resulting formulation of scheduling problems is called a constraint satisfaction problem. It consists of: N variables { X1, X2, . . . , Xn } A range for each variable { R1, R2, . . . , Rn } where range for X1 = R1 = all possible values for X1. Constraints: a constraint Ci involves a relation between a subset of {Xi, . ., Xj} and is satisfied (not violated) if the relation holds for a set of values for these variables. * Types of constraints There are many types of constraints for scheduling problems. Some of the more notable include task/job ordering, start times, completion times, resource requirements, task reduction requirements, and state requirements. * Types of performance measures If the scheduling problem has many solutions it may not be sufficient to provide the first solution available. Instead it may be desirable to give the best solution based on some performance measure after a certain amount of search. Some performance measures that used include least number of violated constraints, shortest schedule, maximum resource utilization, and least job lateness. A few of these may be combined into a composite measure with the addition of weighting factors for each individual measure. * Constraint Satisfaction Representation of The Job Shop Problem Jobs are variables (say 5) { X1, X2, X3, X4, X5 } Ranges for all R is {1 to 5} [corresponding to positions in the order] Constraints 1. only 1 variable may be assigned position 1 2. only 1 variable may be assigned position 2 3 only 1 variable may be assigned position 3 4. only 1 variable may be assigned position 4 5. only 1 variable may be assigned position 5 6. all variables must be assigned Performance Measures: Shortest Schedule Possible SCHEDULING AND RESCHEDULING WITH ITERATIVE REPAIR Jobs each requiring | n-tasks | . 5| t1 | Resources | \|/ . 4| __ . 3| ___ . 2| . 1| . |________________________________________ State Variables | . 3| . 2| . 1| . |________________________________________ Above is a visual representation of the Space Suttle problem. For this problem Zweben et al. used an iterative repair method to derive a schedule with the least number of constraint violations. Rescheduling with iterative repair begins with complete, but possibly flawed, set of assignments and then iteratively changes the assignments to improve the schedule. The program which was created for the scheduling task was a form of constraint-based iterative repair. The variables for this problem are the tasks to be scheduled. Each task has a start time and a completion time associated with it. The constraints are mainly of three types: ordering constraints, resource constraints, and state requirements. In addition to these, preemptive constraints may become necessary due to certain time period assignments for a task. A preemptive constraint involves the splitting of tasks into subtasks where certain state requirements and resources must be maintained between the subtasks. The requirement to maintain the state or resource condition is called a preemptive constraint. Preemptive constraints modify resource and state constraints so that preemptive intervals may be maintained. It is through this modification of resource and state constraints that preemptive constraints are employed in Gerry. As for the other constraints, a resource constraint violation has to do with over utilization. Each resource has an associated capacity. In the diagram above t1 of job1 requires resources 3 and 4. If t2 of either job3 or job5 requires resource 3 or 4 then it must be determined if the resource has the capacity. If it doesn't then this is a violation of the resource during that time frame. A state voilation results if a system variable is not set correctlty. The performance measure for Gerry is to minimize the number of resource and state constraint violations. The importance of a particular violation depends on whether it is a resource or a state constraint violation and on how bad the constraint is violated. The constraint cost function is Cost(s) = Sum( penalty(s).c1 * weight.c1) for all ci where s = solution and ci are the individual constraints. The penalty function returns a value for the degree to which the constraint is violated. The weight represents the importance of the constraint. Solutions which have lower costs over previous solutions are consider more desirable. The algorithm used in Gerry starts with a complete schedule and tries to lower the cost by rescheduling certain tasks. Tasks which have the greatest effect on the cost function are rescheduled to the period before and after its current begin and completion times. After ordering constraints are adjusted with the Waltz algorithm the cost of the new schedule is calculated. If the new cost is less than the current cost it is accepted. If the new cost is worse than the current cost it is accepted if a random number between 0 and 1 is greater than a number from an escape function. This is a attempt to avoid local minimums using simulated annealing. While this paper presented this "novel" approach to scheduling its stated purpose was to analyse the effects of knowledge in search. Four different approaches were compared in an effort to demonstrate the effects of knowledge. The first was to take any task and reschedule it and use the new schedule if it was an improvement. The second method was to reschedule tasks which had the greatest impact on the above cost function. The tasks were reschedule randomly. If the new solution was an improvement it was kept. The third method was the iterative repair method discussed above. The fourth method was the look ahead method MIN-CONFLICTS. Based on experimental results the authors concluded that knowledge influences search. That some knowledge improves the quality of the solution but that too much degrades the results. This paper provides a description of an interesting problem. In addition, the iterative repair method and the results of the experimentation are interesting. However, the paper provided only a superficial description of the heuristic. Many details were left to the imagination of the reader. 10/20/95