A Planning/Scheduling Methodology for the Constrained Resource Problem

1 Introduction

Many artificial intelligence tasks can be formulated as the constraint-satisfaction problem ( CSP) which involves the assignment of values to variables subject to a set of constraints. The CSP consists of a finite set of n variables (or tasks) VI' ... ' vn, a set of domains D1 , ··. , Dn, and a set of constraint relations C 1 , ··· , q. Each D; defines a finite set of values (or labels or solutions) that variable v;. may be assigned. A constraint C; specifies the consistent or inconsistent choices among variables and is defined as a subset of the Cartesian product:

1 This research was sponsored in part by the Derense Advanced Research Project Agency under contract MDAll03-86-0182.

In this paper the goal of the CSP is to find one tuple from D1 x · · · x Dn such that n assignments of values to variables satisfy all constraints simultane­ ously.

In the process of solving a CSP, two decisions have to be made at each cycle, i.e. which variable to instantiate next and which value to assign to that vari­ able. Since heuristics are used to guide these decisions in solving difficult CSPs, backtracking is usually una­ voidable. If the cost of backtracking is high, the prob­ lem of how to reduce the amount of backtracking become crucial. Intelligent backtracking such as dependency-directed backtracking in truth mainte­ nance systems [Doyle, 1979] is one way to deal with the problem. For problems in which the dependency relation is complicated, however; dependency-directed backtracking may be ineffective. An example that illus­ trates this behavior is N-queens problem in which every decision depends on all previous decisions. An alternative to dependency-directed backtracking is to give good advice for each decision so that the number of backtracks can be minimized. Various strategies for this have been developed. For variable selection, [Bitner, 1975, Haralick et al., 1980, Purdom, 1983] try to order uninstantiated variables dynamically in every branch of the search tree so that the next variable is always the one that will most constrain the rest of the search tree. Usually the variable that has the least number of values left is selected. In value assignment, Dechter [1988] attempts to assign a value that maxim­ izes the number of options available for future assign­ ment. Dechter identifies classes of constraint graphs lending themselves to backtrack-free solutions and dev­ ises efficient algorithms for solving them. By selec­ tively deleting constraints from the original constraint graph, the original problem is then transformed into a simplified and backtrack-free problem. The number of consistent solutions in the simplified problem is there­ fore used to establish priorities of value assignments to variables in the original problem.

A subclass of CSP -- the constrained resource problem ( CRP) -- supplies significant information that may be used to guide the search. This information has not been used in previous approaches. In CRP, vari­ ables are tasks and values are resources. In this frame­ work, two important characteristics of the problem are limited resources and non-sharable resources, i.e. a value can only be assigned to one variable and the total number of values is limited. The N-queens prob­ lem is an example of CRP if we assume that the rows are tasks and the columns are resources. In CRP the tasks are competing for the limited resources, i.e. the tasks interact. These tasks have to work cooperatively in order to find the solution for the problem. Both the task selection and the resource assignment should be guided in the way that:

1. the possibility of success in the future is maximized;
2. the amount of backtracking is minimized.

In order to achieve these goals we require some meas­ ures for how task competition affects individual tasks and we must use these measurements to guide the deciSlOnS.

In this paper we propose an approach for CRP that is different from Dechter's and others. We demonstrate the approach and show its effectiveness on the N-queens problem. We then generalize the approach to solve the general CRP in which the solu­ tion for a task may contain more than one resource.

2 A Planning/Scheduling Methodology for CRP

The CRP consists of a finite set T of n tasks T1 , .. . , T,., a set D of domains (or solution space) D1 , .. . , D,., a finite set R of resource units r 1 , . . . , r m, and a set C of constraint relations C1 , · · . , C,. Each D; defines a finite set of solutions P; 9 , . . . , P;t that task T; may be assigned. Each P;k can satisfy T; and consists of a resource unit rk·

Due to the heavy interactions among tasks in CRP, the way in which resources are assigned to a task greatly impacts the possible resource assignment of other tasks. The problem solver searching for the local optimal solution without considering the global consequence of the solution suffers from:

• ( 1) myopia with respect to only a specific task interaction;
• premature commitment of resources to the task, thereby constraining the future possi­ ble resource assignments of the remaining tasks and the final solution.

Myopia and premature commitment often arise from implicitly or unnecessarily predetermined orderings on search control, rule firing, resource priority or ignorance of global interactions in the problem. They increase the chance of making wrong decisions at the early stage of the planning/scheduling process, conse­ quently increasing the amount of backtracking and the overall cost of problem solving.

The traditional least commitment strategy, as used in the current literature [Sacerdoti, 1975, Tate,

1977, Stefik, 1981], attempts to make a commitment only if there is a clear reason for doing so. The CRP is underconstrained and there is usually more than one alternative for the direction in which to proceed. The least commitment strategy is insensitive to these dis­ tinct needs, and is hence incapable of dynamically han­ dling the interactions, in a situation-specific manner. Therefore, in order to provide the flexibility of dealing with task selection separately from solution selection, while continuing to monitor and handle the interac­ tions between the two decision phases, we propose two domain independent policies - most-constraint and least-impact - to govern task selection and resource assignment respectively. The most-constraint policy tries to select the task which has least chance to sur­ vive under the resource competition. The least-impact policy attempts to select a resource which needs the least cost to use up that resource. These policies can avoid myopia and premature commitment by doing situation-specific reasoning that is sensitive to task interactions. The task interactions, in turn, are modeled by considering the criticality of the task, the cruciality of the solution, and constraint propagation, as described below. The planning/scheduling meth~ dology can then be represented by a "four-corner" model shown in Figure 1. The planner /scheduler repeats the following four steps. Starting with a current agenda,

1. Select the most critical task by the most­ constraint policy.
2. Formulate the solution space (feasible solutions) for the selected task.
3. Select the least crucial solution from the current solution space by the least-impact policy.
4. Commit the resource to the selected task and propagate constraints (generating a new agenda and updating the status of the tasks and the resources).

2.1 Criticality of the Task

Each task is associated with a value called criticality which measures the impact of task interactions. The criticality of a task considers not only the number of possible resource assignments for the task, but also the impact from other tasks that are competing for the same resources. Task criticality measures the degree of flexibility for a task, i.e. the degree of survivability for a task that is constrained by resource competition and earlier commitments. The higher the criticality, the more flexible the task, and therefore the less criti­ cal the task. The most-constraint policy selects as the next task the most critical one. Task criticality is updated at each cycle since each commitment for a task reduces the number of possible resource assign­ ments of the remaining tasks, due to the diminishing resources and the constraint relations. Hence, the cri­ ticality for each task is sensitive to any previous com­ mitments.

Let the operation ASSIGN( T;, r") represent the attempt of assigning r" to T;. Let a ik be the degree of need (or demand or competition) for r" by T;. There­ fore, a;"= 1 I ID;I for all r" E D;. Let ..,ik represent the strength of the impact/competition to ASSIGN( T;, r") from all unachieved tasks. Thus, .., .. " =a;~~:+ E ail · where Ti has possible resource assignments ASSIGN( Ti, r1) which is in conflict with ASSIGN( T;, r~~:). That is, all unachieved tasks express their degree of dislike to the idea ASSIGN( T;, r~~:) or their strength of the need/ compeJ,ition for r~~:. Accord­ ingly, a;~~: I ..,ill: represents the survivability for ASSIGN( T;, r~~:) from the competition. Therefore, il; = E (a ik I .., ik) where il; represents the criticality

" of T;, with respect to all possible assignments r" to T;, r" E D;. The task having smallest criticality is the most constrained task and is selected as the next job. The solution space of the selected task T; is the current corresponding domain D;.

2.2 Cruciality of the Solution

Each individual solution is associated with a value called cruciality that measures the impact to the rest of the tasks if we commit a resource to a task. The cruciality of a solution is the cost of using up the resource in the solution. That is, in order to commit a resource to a task, we may have to give up several pos­ sible solutions for other tasks. The higher the crucial­ ity of a solution, the more competitive the resource unit in the solution. The least-impact policy selects the solution having least cruciality for the chosen task, hence the commitment of that solution has a minimal impact on the remaining tasks. The cruciality of the solution is updated at each cycle because each commit­ ment for a task may disable a resource unit , conse­ quently increasing the criticalities of the affected tasks and changing the solution crucialities of unachieved tasks. The cruciality of the solution, therefore, is not only sensitive to the resource demands of unachieved tasks, but also sensitive to any commitment made ear­ lier.

For the current task T;, let r,." represent the cru­ ciality of the solution P;" which contains r~~: . r ... = .., ill: - a ill:. wher-e .., ill: and a ik has been defined above. That is, the commitment of ASSIGN( T;, r~~:) is on the cost of reducing possible solutions of remaining tasks, i.e. reducing the flexibility of some remaining tasks. The solution having smallest cruciality has the least impact on the unachieved tasks and is hence com­ mitted to T; .

2.3 Constraint Propagation

At each planning/scheduling cycle, the current environment should be consistent, i.e. no constraints should be violated and all unachieved subgoals should have at least one potential solution. Committing a solution, however, imposes new constraints (e.g. dis­ ables some resources) on the current environment. The current environment, therefore, has to be updated in order to reflect these changes. (One special case, called the domino effect, occurs when the impact of committing one task prunes another task's solution space to an unique solution.) Accordingly, a new con­ sistent environment is generated or an inconsistency is found, which means a task is overconstrained. In that case, we retreat to the most recent choice point for which alternatives exist and make a new choice (i .e . retreat counterclockwise along the four-corner model).

3 An Example: theN-queens problem

We formulate the N-queens problem as a N x N board. Each position in the board is denoted by ASSIGN(R;, c") where R; and c~~: represent the ith row and the kth column respect ively. The tasks of the problem are rows and the resources are columns. The goal is to find a N tuple of consistent positions for N queens. Let D; be the domain of row R; where D; con­ tains all possible column assignments to R; . For all c~~: E D;, a;"= 1 I ID;i and hence..,,."= E ail where I= k (same column) or li - il = ik - II (diagonal). Therefore I n,. = E (a ik I .., ik) where n,. is the criticalIf:

ity of R; and Cif: E D;. rill: = .., .. 11: -a;~~: where rill: is the cruciality of ASSIGN(R;, c~~:)

We have implemented the proposed approach in C on a SUN 3/260 running 4.2 BSD Unix and tested it on board sizes ranging from N=4 to N=lOO. We compare the results with those generated by an approach which uses two simple heuristics to guide the row selection and column assignment . The heuristic for the row selection chooses the row having least number of possible column assignments. The heuristic for column assignment selects the column whose assign­ ment maximizes the number c;,f possible column assign­ ments for remaining rows. For both approaches, ties are broken via the natural ordering of the indices. Fig­ ure 2(a) shows the number of backtracks as function of the problem size. The small o's and x's represent the numbers of backtracks generated by our approach and simple heuristic method, respectively. Figure 2(b) plots the execution time as functions of the problem size. The dashed line denotes the execution time of the program using the simple heuristic method, while the solid line indicates the execution time using our approach.

Using our approach, no backtracking was per­ formed 76% of the time, the maximum number of backtracks in any single case was 13, and the average number of backtracks was less than 1. This indicates that our approach is usually successful in guiding the search in the right direction, especially at the early stages of the process. For the simple heuristic method, backtracking was performed 80% of the time, the maximum number of backtracks was more than 10 8 , and there were 4 cases whose numbers of backtracks were more than 10 4 · This indicates that. the perfor­ mance of the simple heuristic method is very unstable. In contrast, the performance of the proposed approach is consistent in the test cases. The main reason is that the number of possible column assignments for each row does not express the actual flexibility of the row. That is, the simple heuristic method makes decisions based on insufficient information that does not con­ sider the impact of resource competition. Conse­ quently, in several cases, it made wrong decisions at the very early stages of the process and thus, the sim­ ple method had long execution times due to the extremely large numbers of backtrack.

Our approach incurs considerable overhead in computing task criticality and solution cruciality. The number of backtracks is diminisped to such an extent, however, that our approach is frequently competitive (and occasionally outperforms) the simple heuristic, even when backtracking is very cheap, as in the N­ queens problem. For problems where backtracking is expensive, the strength of our approach is likely to be demonstrated more persuasively. There are, however, opportunities for reducing this overhead significantly by parallelizing these computations since all the com­ putations for task criticalities and solution crucialities are independent.

4 Model Generalization

Our model can be generalized to more general class of CRP in which a task may demand more than one resource unit. That is, each Di defines a finite set of subplans Pi1 , . .. , Pit· Every Pii consists of a different set of resource units {r4 1 r4E X}.

Let ~it be the number of solutions including resource unit r4 in Di, i.e. the importance of r4 to Ti is increasing while the number of solutions that need r4 is increasing in Di. Thus, Ctit =~it/ IDil and 'Yit = etit + E ail where ASSIGN(T;,rt) is in conflict with ASSIGN( Ti, r4} due to resource competition or the constraint relation. Let w if be the criticality of

Ct .· solution Pii· wii = Min _ _!_ where r4E Pii· Since a · 'Y i/r solution may contain more than one resource unit, we define the criticality of the solution to be the surviva­ bility of the most competitive resource unit. There­ fore, the criticality of the task is the sum of the criti­ calities of their possible solutions, i.e. {}i = E wii· i For selected Ti, solution cruciality is the impact of committing pii to other tasks. rii = Ehit - Ctit), ·

where r4E Pii· With these modified definitions of task criticality and solution cruciality, our planning/scheduling model can be applied to the gen­ eral CRP.

5 Other Applications

We have attempted to apply our model to several CRP& such as VLSI switchbox routing and job-shop scheduling. In this paper we only formulate the CRP model for these two problems. Our executable model can then be applied to these problems according to the definitions described above.

5.1 Switchbox Routing Problem

Switchbox routing [Burstein et al., 1983, Ho et al., 1985] is an important task in the physical design of VLSI chips. The problem is formulated on a rectangular-grid with fixed-position net terminals on each of the four edges. Each terminal is identified by the name of the net to which it belongs and each net contains at least two terminals. A track is a line seg­ ment between two grid points and there are two rout­ ing planes. One plane contains horizontal tracks and the other one contains vertical tracks. Connection between a vertical track and a horizontal track is made through a small hole called via. Different nets cannot contact one another on the same layer. The task for the switchbox router is to connect all of the terminals with the same net name.

In switchbox routing, tracks and vias are resource units, while tasks correspond to the connect­ ing of pairs of terminals. For each pair, the coordi­ nates of the two terminals define four edges of a rec­ tangle, i.e. demand block (DB), in which the two termi­ nals are two opposite vertices. Each pair demands tracks and vias in the rectangle. The solution space of a pair contains all shortest paths connecting the pair in the rectangle. A path consists of at least one track. The application of our model, as well as the implemen­ tation and results have been presented in [Ho et al., 1985, Keng et al., 1987].

5.2 Job-Shop Scheduling Problem

The job-shop scheduling problem [Baker, 1974, Fox, 1983, Keng et al., 1988] consists of a set of machines and a set of orders of products. For each product, a partial ordering (process routlng) of operations whose execution results in the completion of the product is given. For each order, the scheduler assigns a time interval (start and end times) and a machine to each operation in its corresponding process routing. The task for the job-shop scheduler is to construct a schedule in which all orders are finished.

The set of resource units contains (machine, time) pairs {(M1, t11 ), .·· , (Mm, tm.)}, where tii denotes the time unit j on machine M;. Each machine is asso­ ciated with a time horizon that is divided into consecu­ tive time units. The set of tasks are operations that are obtained through decomposition of the set of ord­ ers and their corresponding process routings. The pre­ cedence relations among operations are constraints. For each operation we can compute the resource demand, i.e. demand window (DW'), that defines the earliest possible start-time and the latest possible end­ time for the operation, using the ready time and the due date of the corresponding order. DW defines all possible time intervals that can be assigned to the operation and is the solution space of the operation. A time interval consists of at least one resource unit. A detailed discussion of the application of our model to the job-shop scheduling problem is found in [Keng et al., 1988] .

6 Conclusion

A dynamic planning/ scheduling methodology for the CRP has been presented in this paper. Our model uses two domain independent policies -- most-constraint and least-impact-- to control the search for a solution. The most-constraint policy controls the selection of the next task according to the task criticality that meas­ ures how task competition for resources constrains a task. For a selected task, the least-impact policy guides the search for the solution according to the solution cruciality, that measures how the commitment of a solution affects the possible resource assignments for other tasks. The criticality and the cruciality are sensitive to the dynamically changing environment, because they are updated after each resource commit­ ment and rearranged according to their new priorities. Consequently, our model acts opportunistically and in a constructive, situation-specific manner, without mak­ ing premature commitment.

Experiments indicate that our approach is usu­ ally successful in guiding the search in the correcL direction. In a set of 97 test cases using the above model, no backtracking was performed 76% of the time and the maximum number of backtracks in any single case was 13. Our model is likely to be highly appropriate for problems where the cost of backtrack­ ing is high. Our approach does incur considerable overhead in performing the analysis required for deci­ sion making, however there are opportunities for reducing this cost by parallelizing the computations of task criticality and solution cruciality.

The problems to which our model has been suc­ cessfully applied includes the VLSI switchbox routing problem [Ho et al., 1985, Keng et a/., 19871, the job­ shop scheduling problem [Keng et al., 1988 , the task assignment problem in parallel processing [Tsai, 1988] . By using two control policies and uniform representa­ tion to measure the resource competition among tasks, our methodology not only has provided realistic and executable planning/scheduling guidelines for CRP problem solvers, but also has enhanced the operability and measurability of problem solving by planning/scheduling. Hence, we believe our model presents a general methodology for problem solving by planning/ scheduling.