Cyclic Scheduling

1 Introduction

A cyclic scheduling problem is a scheduling problem in which some set of activities is to be repeated an indefi­ nite number of times, and it is desired that the sequence be repeating. Cyclic scheduling problems arise in do­ mains such as manufacturing, time-sharing of processors in embedded systems, and in compilers for scheduling loop operations for parallel or pipelined architectures. In this paper, we will take the manufacturing domain as our motivation and address the cyclic version of the job shop problem, in which a set of tasks (which describe the building of a single widget) are to be scheduled into a cyclic schedule for a widget factory.

Cyclic scheduling has not received much attention in the AI community, but there is a considerable body of David E. Joslin i2 Technologies 909 E. Las Colinas Blvd. Irving, TX 75038 david_joslin@i2.com work available in the OR literature; [Hanen and Mu­ nier, 1995) gives an excellent overview. Many heuris­ tic approaches have been suggested for particular prob­ lems such as hoist scheduling, but there is also work on representations for general job shop problems, such as [Hanen, 1994) and [Roundy, 1992]. We do not have the space in this paper to fully describe their approaches, but the common element involves building a special-purpose data structure which represents the problem, and solv­ ing it using techniques such as branch-and-bound search or mixed integer programming.

*This work was done while this author W!JS at Rockwell Palo Alto Lab.

tsome of this author's contributions to this work were made while at Rockwell and with support through CIRL.

In this paper, we will describe a different approach to the cyclic scheduling problem, one which is a con­ ceptually simple extension of the constraint-based for­ mulation of scheduling problems that has enjoyed much recent success. The main advantages to using such a constraint-based framework are the availability of exist­ ing techniques and the extendability of constraint-base_d representations. This allows us to transparently explmt the power available in any of the modern constraint satis­ faction search engines, utilize other constraint reasoning techniques such as constraint propagation and consis­ tency checks, and use the problem formulation within larger constraint decision problems. We also find that the formulation lends itself to the use of methods for recovering schedules after a failure, and that it can be extended to handle more complex problems such as re­ source constrained project scheduling.

We will start with a brief description of the now­ standard constraint formulation of job shop scheduling, and then go on to present our extension to handle cyclic scheduling problems. We then present experimental re­ sults on solving such cyclic scheduling problems, and briefly discuss two extensions to our approach.

2 Job Shop Scheduling

The job shop scheduling problem can be found in many standard texts (e.g. [Baker, 1974]); the problem is speci­ fied by a set of tasks, T, and a set of resources, R. There is a function on tasks, dur(t), specifying a non-zero du­ ration for each task, and a predicate u( t, r) specifying whether task t uses resource r. 1 Finally, there is a set of precedence constraints, where each constraint ti < ti specifies that the task ti must be completed before the task ti can begin. A valid schedule is an assignment of start times to each task such that the precedence con­ straints are obeyed and no two tasks require the same resource at the same time. The completion time of the final task in the schedule is called the makespan of the schedule. The goal of scheduling can either be satisfic­ ing (find a schedule whose makespan is at most D), or optimizing (find a schedule with minimal makespan).

The satisficing scheduling problem can be encoded as a constraint satisfaction problem, and solved using search or a combination of constraint propagation and search, and the optimizing scheduling problem can be solved with additional search or branch-and-bound over pos­ sible makespans. Early approaches focused on search­ ing over the space of start times for tasks. More recent approaches have found it more efficient to search over ordering decisions between tasks-once sufficient order­ ings have been added to guarantee that the resource con­ straints have been satisfied, it is simple to determine a minimal start time for each task consistent with those orderings.

3 Cyclic Job Shop Scheduling

In the job shop scheduling problem, the set of tasks is fixed as given. For the cyclic job shop problem, we as­ sume that the set of tasks is a template which we wish to repeat indefinitely-for example, the tasks represent the steps to build a single widget, and we wish to con­ struct a schedule for a widget factory. In order to make efficient use of our resources, we will want to overlap the manufacture of multiple widgets. A cyclic schedule for building widgets is one in which a new widget is begun every K time units (the cycle time), and the same sched­ ule of tasks is completed for each widget. Assuming the time to complete each individual widget is greater than K, the result is a pipeline in which multiple widgets are under construction at any one time.

It is not the case that a cyclic schedule is necessar­ ily the most efficient schedule; for any fixed number of widgets, N, a non-cyclic schedule for building N wid­ gets might very well exist that is more efficient than any cyclic schedule [Hanen, 1994]. Even if we do not knowN in advance, we could still use anN-widget schedule as an approximation, repeating it as necessary. There are two significant advantages to using cyclic schedules, however.

1 Note that this approach to representing resource usage allows for tasks requiring more than one resource, which is a commonly used extension to the standard job shop problem.

The first is that cyclic schedules are much easier to im­ plement: it is easier to communicate a short, repeatable sequence of actions to the agents which must carry them out, than to specify a much longer, non-repeating se­ quence. Secondly, the cost of computing optimal sched­ ules for N widgets grows exponentially with N , while the cost of finding a single widget cyclic schedule to make N widgets is independent of N . Furthermore, as we shall see, the complexity of our cyclic algorithm has in the worst case only an extra logarithmic factor over the ba­ sic job shop algorithm. 2

In order to explain our cyclic scheduling formulation, we will start at the end, with some observations on cyclic schedules. The main observation is that any assign­ ment of start times to tasks that satisfies the resource constraints can be converted into a cyclic schedule. For example, consider the scheduling problem specified in Figure 1(a). Figure 1(b) shows an assignment of these tasks to resources. To convert this assignment into a cyclic schedule, paste copies of the basic cycle together into a strip in such a way that they do not overlap­ this induces a cyclic schedule with some particular cycle time, as shown in Figure 1(c). Then, no matter what task ordering was chosen, or what cycle time is induced, it is possible to overlay a complete schedule for one single widget such that the precedence constraints are satisfied; this is done in bold in Figure 1(c). A simple counting argument shows that this is a proper cyclic schedule for this set of tasks: every task is fulfilled, and there are no tasks left over.

2 An interesting compromise between computation cost and optimality is to build cyclic schedules for building two or more widgets at a time.

This exercise demonstrates several things. First, whereas the makespan is the only measurement of in­ terest in the traditional job shop schedule, in the cyclic case we have two: the cycle time K, and the latency, L, which is the number of cycles required to complete a sin­ gle widget (which is also equal to the number of widgets in production simultaneously).

Secondly, notice how the precedence constraints were satisfied. For any precedence constraint ti < ti, it is either the case that ti and ti occur within the same cy­ cle, in which case the 'normal' precedence holds between them, or it is the case that ti is in one cycle, and ti is in a subsequent cycle. (In Figure 1, the precedence con­ straints A< B , A< D, C < E, and D < E are satisfied 'normally,' while constraints B < C and E < F cross cycle boundaries.) 3 The point is: in order to satisfy a constraint ti < tj, we can either order ti before ti within a cycle, or defer the execution of ti to the subsequent cy­ cle. This observation is the basis of our cyclic scheduling formulation: we will restrict our attention to scheduling of tasks within a single cycle, modifying the definition of the precedence constraint to allow for the two different ways in which it can be satisfied.

With this formulation, we can employ any standard search procedure. There are no new decision variables: we search only over orderings of steps within a cycle. We can do satisficing search for both a given cycle time K and latency L, or we can optimize cycle time for fixed latency or vice versa, or we can search for a set of dom­ inating solutions in both K and L.

We will now lay out our constraint encoding formally, and introduce some additional variables and consistency checks to avoid redundant or useless search.

The inputs are:

• t1, ... , tn: the set of tasks,
• r1, ... , r m: the set of resources,
• dur(t) : the duration of each task,
• u(t, r) : usage predicate for each task/resource pair,
• { ti < t i, ... } : a set of precedence constraints on task pairs,
• K: the cycle time,
• Lma:r:: maximum allowable latency (optional).

The decision variables we search over are:

3 We have to be careful about tasks which overlap cycle boundaries, such as task D; we will address this below.

• o(ti, ti): ordering predicate on pairs of tasks within a single cycle. ·

We use the following non-decision variables for consistency checking:

• st(t): start time oft wrt the beginning of a cycle,
• cs(t): cycle in which the first instance oft starts,
• cf(t): cycle in which the first instance oft finishes.

Cycles are numbered from one at the beginning of the schedule; cs and cf measure the positions of the begin and end of each task for the first widget (e.g. in Figure 1 we have: cs(D) = 1, cf(D) = 2, and cs(F) = 3). Note that cs and cf are only required if there actually is a desired limit on latency, which we will assume to be the case.

For conciseness, we will add notation to represent the condition that a task crosses the cycle boundary:

The constraints we must satisfy are as follows:

1. The start time of each task is within the cycle:

1. If task ti is ordered before task tj, then the termi­ nation of ti in the cycle occurs before the start of ti in the cycle.

It is possible for both o(ti, ti) and o(ti> ti) to hold, if either task crosses the cycle boundary.

1. If two tasks use the same resource, one must be ordered before the other; if either task crosses the cycle boundary, they must be ordered in both direc­ tions, and both tasks cannot cross the cycle bound­ ary.

1. If a precedence constraint ti < ti exists, then either ti is ordered before ti, or ti is deferred with respect to ti, which means that ti must start in a cycle that comes after the cycle in which ti finishes .

1. If a task crosses a cycle boundary, its finish cycle number is one greater than its start cycle number; otherwise they are the same.

1. The cycle numbers must be between one and Lma:r::

When solving this problem, we initially assign possi­ ble ranges to the variables: st(t) E (0, K), cs(t), cf(t) E {1, . .. ,Lmaz}, and o(ti,tj) E {true,false}. Then we search over assignments to o( ti, t 3), using consistency propagation techniques to prune the possible values of all the variables. When enough ordering variables have been set such that all the required constraints are guar­ anteed to hold, we take start times and cycle numbers to be the minimal of their remaining possible values.

This description is complete, but misses some impor­ tant details concerning the efficient pruning of the sup­ porting variables.

In the standard job shop constraint formulation it is customary to keep, in place of a set-valued st(t), two variables-earliest possible start time, est(t) and lat­ est possible start time lst(t)-which represent the end points of st(t). The value of est(t3) can be efficiently updated by using the rule

(and a symmetric rule for lst(t)) . The advantage of this representation is that the updated values for est(t) and lst(t) can be computed quadratically in the number of tasks by traversing them in topological order (for est(t)) and reverse topological order (for lst(t)).

In our formulation of the cyclic scheduling problem, we also use est(t) and lst(t) to represent the end points of st(t), and we use essentially the same rules for updating these variables, except that we now must account for the cycle boundary by introducing a mod K. But, since the ordering decisions o(ti, t3) may have a cycle, the propa­ gation may not terminate at the end of the schedule, as it does for standard job shop problems. For an example, consider a task A that crosses the cycle boundary and as a result forces an increase in the earliest start time for another task B. If moving B then ultimately results in changing est(A), the standard propagation will continue propagating this cycle, until est(A) reaches K. How­ ever, we note that when the task sequence for a resource is moved more than once, the current schedule is proven to be infeasable and the propagation can therefore be halted immediately.

Our treatment of the cs(t) and cf(t) follows a similar pattern: we keep two variables to implement the lower and upper bounds on each quantity. To update the val­ ues for ecs(t) and ecf(t), we initially assign each variable to zero, then do two passes. In the first pass, ecf(t) is updated using constraint 5 above-that is,

In the second pass, we consider the precedence con­ straints in topological order. For each precedence con­ straint, we enforce the following constraints:

Each time one of these constraints increments ecs(t), we reinforce constraint 5 by incrementing ecf(t) by the same amount.

The computation of lcs(t) and lcf(t) follow a sym­ metric pattern, initializing from constraint 5 and lst(t), and updating by considering the precedence relations in reverse topological order.

The algorithm described above produces a schedule for a fixed cycle length K. In order to optimize over K, we must iterate the scheduling process over possible values of K. An upper bound on K is given by the makespan of the problem, treated as an ordinary job shop scheduling problem (which could be bounded or approximated by any number of means) . A lower bound forK is given by the largest total time requirement for any one resource (at which point that resource is 100% utilized).

The worst-case complexity of this algorithm, for a sin­ gle value of K, clearly differs from the complexity of the ordinary job shop scheduler by only a small constant factor (required to process the additional constraints for computing cycle numbers). If we assume that the cy­ cle time and the task durations are all integers, we can bound the worst case time required to search over multi­ ple values of K by Tlog(Kmaz- Kmin) , where Tis the time to invoke the scheduler for a single instance of K .

4 Experimental Results

It is clear that cyclic schedules have a number of ad­ vantages over non-cyclic schedules in applications where schedules are repeated. The question is whether the cost of generating cyclic schedules is reasonable enough that these advantages can be realized. To verify that this is indeed the case for our cyclic scheduling formulation, we compare the cost of solving problems using our formula­ tion to the cost of solving the same problems using the smaller classical formulation, with the goal of minimizing the cycle length. The comparison is done by applying an optimization search method (branch-and-bound with a time cutoff) to each formulation of a given problem and comparing the resulting cycle length. For the standard formulation, we calculate the cycle length as the longest distance between first and last use of a resource, since a new widget can be started at those intervals. 4

The scheduling problems used in this comparison are from Norman Sadeh's scheduling test suite [Sadeh, 1992]. Disregarding the makespan limits, which are irrelevant when minimizing cycle time, the suite gives us 20 dif­ ferent problem instances. Each problem has 50 tasks, each task uses exactly one resource and there are 10 re­ sources in all. It should be noted that these particular problems are not all that hard for modern search tech­ niques and well-honed heuristics [Crawford and Baker, 1994]. But, the question here is not whether our formu­ lation outperforms existing engines or heuristics for job shop scheduling; the question is whether this larger cyclic constraint formulation can be solved efficiently enough that the benefits still outweigh the possible increase in solving time. For answering that question, these schedul­ ing problems are a perfectly suitable testbed.

4 Note that for the standard formulation, the cycle length also replaces makespan in all pruning and heuristic calcula­ tions. In all other aspects,. the search proceeds as usual; or­ dering decisions are made such that resource and precedence constraints are satisfied.

To solve the two different formulations of the schedul­ ing problems in the same manner, we use the gensolve system [Jonsson, 1997], which is currently a prototype of a general constraint satisfaction system that can use ar­ bitrary combinations of procedural propagation methods to speed up the search effort. In this system, problems are represented by providing the decision variables, the constraints on value assignments, and procedures that perform propagation. For both scheduling formulations we use procedures to determine the possible start times for tasks; in the regular formulation we use the standard propagation of earliest and latest start times, while in the cyclic formulation we use the propagation algorithm described above (with a latency limit of Lma:r: = 2) . In both formulations we use the standard slack-based heuristic described in [Smith and Cheng, 1993].

The key results of this comparison are tabulated in Table 1. The results clearly demonstrate that the cyclic scheduling formulation of these problems can be solved quite effectively by standard constraint solvers. Further­ more, the results show that when it comes to scheduling for cyclic applications, using this new formulation pro­ vides significantly better results than using the standard job shop formulation.

Table 1: A comparison of the effectiveness of minimizing the cycle time using the new cyclic scheduling formu­ lation and doing the same using the standard schedul­ ing formulation. Each problem instance was solved us­ ing a simple version of branch-and-bound search, on an UltraSparc-11, with a time limit of thirty minutes.

5 Extensions

One of the advantages that our approach to cyclic scheduling has over existing special-purpose algorithms is that a general constraint satisfaction formulation can be extended and adapted much more easily. As exam­ ples of this, we will briefly describe how our approach can be extended to the more general class of cyclic resource­ constrained project scheduling problems, and how it can be adapted to provide an approach to recover from fail­ ures in the exectuion of cyclic schedules.

In real-world manufacturing scheduling there are typ­ ically resources that have capacity greater than one (e.g. a pool of skilled labor) , tasks may require multiple in­ stances of each resource type and each task may use multiple resource types. These characteristics have been formalized as the resource constrained project schedul­ ing (RCPS) problem [Blazewicz et al., 1983], which is considered significantly more difficult than the job shop problem.

We would like to extend our cyclic formulation to cre­ ate a solution for the cyclic RCPS problem. We will do this by adapting an existing approach to solving such problems. This approach is based on initially schedul­ ing the tasks without any regard to the resource con­ straints, but respecting the precedence constraints, and then eliminating resource constraint violations by assign­ ing values to corresponding ordering decision variables [Crawford, 1996]. First, let us point out conditions that have changed from the job shop problem:

• Tasks that use the same resource r do not necessar­ ily need to be ordered with respect to each other, if the sum of their usage of r is less than the total availability of r.
• Tasks can have a duration that exceeds the cycle length K, provided that for each task t that uses some resource r with capacity c, we have u( t, r) ~ c and

As a result, a task's cycle finish number can be more than one greater that its cycle start number.

• The lower bound for K is given by the largest to­ tal time requirement for any resource divided by its capacity.

In the cyclic formulation of the above-mentioned ap­ proach, all the tasks are initially scheduled at the begin­ ning of the cycle, without any regard to either resource constraints or precedence constraints. The resource con­ straint violations are then eliminated as before, while precedence constraint violations are resolved by either making the appropriate ordering decision within the cy­ cle or by defering the second task to a later cycle. The impact of each ordering decision is then propagated to restrict the bounds on start times and cycle numbers for later tasks, in a similar fashion as for the cyclic job shop scheduling formulation. Just as for the standard RCPS problems, systematic backtracking methods such as lim­ ited discrepancy search [Harvey and Ginsberg, 1995], or nonsystematic repair methods like · doubleback optimiza­ tion [Crawford, 1996], can then be used to explore the space of decisions.

Turning our attention to schedule recovery, it is well known that optimal or near optimal schedules lack toler­ ance for delays, and thus are easily broken when delays do occur. In the non-cyclic case, we can generate a new schedule from the point of disruption, either from scratch or by modifying the old schedule. However, since one of the goals of cyclic scheduling is regularity, generating an entirely new schedule is not a desirable option. In the cyclic case, we want to focus on returning as quickly as possible to the already-established schedule.

To do this, we consider a rescheduling window, which covers from when the disruption occurs to when the cyclic schedule will be restored. Within it tasks will not follow the repeating pattern used elsewhere in the sched­ ule. The rescheduling window may have jagged left and right edges; any tasks running at the time of the disrup­ tion, but not affected by it, jut into the window from the left side, and any tasks in progress when the cyclic schedule is restored jut into the window from the right side.

The right edge of the window can be determined by incrementing over possible times until a window that is big enough to accommodate the rescheduling is found. In some cases this may be achieved without pushing back the entire schedule. However, if the disruption is big enough, it may not be possible to recover unless the en­ tire schedule is pushed back, thus allowing the recovery more time in which to place the schedule. Once a win­ dow has been established, any search technique can be used to schedule the tasks within it.

6 Conclusion and Related Work

In this paper we have developed a formulation for solving cyclic job shop scheduling problems as constraint satis­ faction problems. We have implemented this formulation and shown that it can be used to generate good cyclic schedules, using standard constraint satisfaction meth­ ods. We have also demonstrated that for the purpose of finding cyclic schedules, the use of our formulation outperforms the use of standard job shop formulations, when the same search technique and shceduling heuris­ tic are applied to both. In addition to this, we have de­ scribed how our formulation can be generalized to cyclic resource constrained project schedules and how the for­ mulation allows us to develop methods for recovering from failures in the execution of cyclic schedules.

As mentioned in the introduction, there are several formulations for cyclic job shop scheduling in the OR community. Furthermore, there exist specific cyclic scheduling techniques in industry, e.g, those used to schedule update cycles on recent Honeywell avionics [Boddy and Goldman, 1994]. We have not been able to do performance comparisons between our approach and other techniques, but the formulation presented here has other clear advantages in terms of understandability, and in terms of being able to exploit existing constraint rea­ soning techniques and heuristics. Perhaps most impor­ tantly, based on this simple constraint representation, further research can build on this formulation. For ex­ ample, by adapting it to more complex scheduling prob­ lems -as we have started doing with the cyclic RCPS problem.

On the other hand, the OR techniques typically han­ dle more complex types of precedence constraints than we do: it is allowed for a task ti to depend on the com­ pletion of a task ti from a different iteration-this is needed for the compiler problem where a loop may con­ tain a statement of the form x[i] := f(y[i-k]). This kind of precedence does not seem to occur in manufacturing problems, our primary interest, but it would nonetheless be interesting to see if this representation can be ex­ tended to handle such more general forms of precedence.