An Iterative Sampling Procedure for Resource Constrained Project Scheduling with Time Windows

1 Introduction

In recent years, CSP scheduling research has been increasingly concerned with development of models for solving cumulative (i .e., multi-capacity resource) scheduling problems. Such models are important be­ cause they are much better matched to the requirements of many practical scheduling environments than tradi­ tional CSP scheduling models. Much of the work in this area has focused on constraint propagation tech­ niques that exploit the structure of cumulative resource constraints, and are hence capable of stronger inferen~e . Less attention has been paid to development of effective heuristics for managing the scheduling search process.

In this paper, we focus on this latter issue. Dra~ing from previous work in resource-constrained scheduling, we develop a base CSP resolution procedure for cumu­ lative scheduling. Our procedure proceeds by iteratively detecting and leveling "resource contention peaks", i.e., periods where demand is projected to exceed resource capacity. The conflict selection and resolution heuris­ tics used in our procedure to direct the search general­ ize those employed in previous "profile-based" schedul­ ing approaches, replacing localized, pair-wise analysis <:>f competing resource requests with more global. analysis of minimal conflict sets. Such extended analysis can be expected to lead to more informed resolution decisions.

Our specific interest in this paper is application of this scheduling approach to the resource constrained project scheduling problem with time windows (RCPSP /max) , a well-studied and difficult makespan minimization prob­ lem. To this end, extensions are developed to enable use of the base resolution procedure within a larger "op­ timizing" search process. Below, we first define the RCPSP /max problem (Section 2). Next, we describe elements of our composite RCPSP /max solution proce­ dure (Sections 3 and 4) . Finally we report comparative performance results on a previously studied set of bench­ mark problems (Section 5).

2 The RCPSP/max Problem

The RCPSP /max scheduling problem can be formalized as follows :

• a set V of n activities to be executed, where each activity j has a fixed duration Dj . Each activity has a start-time Sj and a completion-time Cj that satisfies the constraint Sj + Dj = Cj.
• a set E of temporal constraints betwee~ activity pairs < i, j > of the form Sj - S; E [T;'j'n, T;'jax], called start-to-start constraints (time lags or gener­ alized precedence relations between activities). I
• a set R of renewable resources, where each resource rk has a integer capacity Ck 2: 1.

1 Note that since activity durations are constant values, end-to-end, end-to-start, and start-to-end constraints be­ tween activities can all be represented in start-to-start form.

• execution of an activity j requires one or more re­ sources. For each resource rk the integer rcj ,k rep­ resents the required capacity (or size) of activity j.

A schedule S is an assignment of values to the start­ times of all activities in V (S = (S1, . . . , Sn)). A schedule is time-feasible if all temporal constraints are satisfied (all constraints Sj - S; E [T;j'in, T;jax] and Sj + Dj = Cj hold). A schedule is resource­ feasible if all resource constraints are satisfied (let A(S, t) = {i E VIS;~ t < S; + D;} be the set of ac­ tivities which are in progress at time t and rk(S, t) = LjeA(S,t) rcj ,k the usage of resource rk at that same time; for each t the constraint rk(S, t) ~ Ck must hold) . A schedule is feasible if satisfies both type of con­ straints. The RCPSP /max optimization problem, then, is to find a feasible schedule with minimum makespan MK (where MK(S) = max{C;}).

In [Bartusch et al., 1988], it is shown that finding a feasible schedule alone for RCPSP /max is NP-hard. This difficulty is due to the presence of maximum sep­ arations T;jax . The RCPSP /max problem has been the subject of recent investigation within the Opera­ tions Research (OR) Community, yielding lower-bound analysis [Heilmann and Schwindt, 1997] and a number of branch and bound (B&B) solution procedures (e.g. , [De Reyck and Herroelen, 1998; Mohring et al., 1998; Schwindt, 1998; Dorndorf et al., 1998]). A problem gen­ erator PROGEN/max [Schwindt, 1996] has been made available on the Web together with a set of reference problems [Kolisch et al., 1998].

3 Constructing a Feasible Solution

We begin by specifying a core CSP resolution proce­ dure for generating feasible solutions to instances of RCPSP /max. Our approach follows the same gen­ eral schema as other constraint-posting scheduling ap­ proaches (e.g., [Cheng and Smith, 1994; Cesta et al. , 1998a]). An initial, time-feasible solution is first com­ puted (ignoring all resource constraints) . Resource con­ straints are then super-imposed and an iterative search is performed to resolve all resulting resource conflicts (i .e., sets of activities competing for the same resource capacity over some time interval). On each iteration a particular conflict is selected to resolve, and one ad­ ditional precedence relation is posted to eliminate the contention. The search continues until either a feasible solution is found (i.e., all conflicts have been eliminated) , or until an unresolvable conflict has been discovered (in which case the search fails) .

Clearly, one key to the effectiveness of this greedy search procedure will be the strength of the heuristics used to select and resolve pending conflicts. In this re­ gard, our approach integrates ideas from a previously re­ ported clique-based approach to resource reasoning [La­ borie and Ghallab, 1995] to improve on previously devel­ oped heuristics for cumulative scheduling. A second way in which the effectiveness of above (partial) procedure can be enhanced is through the addition of backtracking or restarting mechanisms, which serve to broaden the search in the event of failure. Exploiting the approach taken in [Oddi and Smith, 1997], we develop a random­ ized variant of our conflict selection heuristic and embed the core resolution procedure within a larger, iterative sampling search. Before elaborating on the design of these aspects of our feasible solution generator, we first briefly summarize the constraint propagation machinery used to support the search.

3.1 Constraint Propagation

A CSP-based resolution procedure integrates two ba­ sic components: a search procedure responsible for re­ fining the current CSP by taking decisions on possible values for variables, and a constraint propagation pro­ cedure that, after each choice of the search, computes implications by updating the status of the CSP and eliminating inconsistent values. In a scheduling prob­ lem like RCPSP /max both temporal and resource con­ straints can be sources of propagation:

Time constraints. Our search procedure manipulates a temporally consistent network of time points, con­ strained initially by the set of temporal constraints identified in Section 2 and further constrained as additional precedence constraints are posted dur­ ing the search. Path consistency in this network is dynamically maintained via all pair shortest path computation, making distance information between any pair of time variables available for use in focus­ ing the search.

Resource constraints. We do not make use of re­ source constraint propagation as is done in some other recent approaches to disjunctive and cumula­ tive scheduling problems (e.g., [Nuijten and Aarts, 1996; Nuijten and Le Pape, 1998]) . This form of deduction can be seen as complementary to our ap­ proach; it could be added in a transparent way to further prune the search space (and potentially im­ prove reported results) . This is one direction of cur­ rent research.

3.2 ESA: A Basic Resolution Algorithm

Figure 1 specifies the basic "conflict removal" procedure used to generate a feasible solution, referred to as ESA (Earliest Start Algorithm) . The algorithm accepts a problem instance (Problem) and an upper bound on the overall makespan (Horizon). It first computes an earli­ est start time solution that assumes "infinite capacity" (ProblemEsT at line 1) and then attempts to incremen­ tally transform this initial time-feasible solution into a resource-feasible solution. At each step, a resource con­ flict still present in the current solution is selected and resolved, by posting a precedence constraint that delays the earliest start time of one of the competing activities.

Contention Peaks on Resource Profiles. Given a time-feasible, earliest start time schedule {ESTsol) , it is straightforward to identify time instants t where the re­ source capacity constraint of a given resource is violated. We say that there is a contention peak on resource rk at timet if condition rk(ESTsol , t) > Ck holds. Intuitively, a contention peak on resource rk characterizes a conflict ,

ESA(Problem, Horizon) 1. ESTsol f- ProblemEsT 2 SetHorizon(ESTsol, Horizon) 3. loop 4. if ResourceFeasible(ESTsol) 5. then return(ESTsol) 6. else 7. if ExistUnsolvableConflict(ESTsol) 8. then return(EmptySolution) 9. else 10. Conflict f- SelectConflict(ESTsol) 11. PrecC f- Select Precedence( Conflict) 12. Post&Update(PrecC,ESTsol) 13. end-loop 14. end

identifying a set of activities that simultaneously require rk but have a combined capacity requirement > Ck .

Obviously feasible solutions do not contain peaks, and one possible way to transform ESTsol into a feasible so­ lution is to detect and remove all peaks. This is the basic idea behind profile-based scheduling procedures [Cesta et al., 1998a]. A peak can be removed by "leveling" it, that is by posting one or more precedence constraints between pairs of activities contributing to the peak (such con­ straints are posted between the end-time of one activity and the start-time of the other to avoid overlap). In lev­ eling a conflict , the choice of which pair(s) of activities to order can be quite crucial to the quality of the solu­ tion, as it is possible to add precedence relations that do not have a strong peak leveling effect . For example, assume resource rk with capacity Ck = 4 has a peak that includes the following activities (capacity requirements in brackets) : {a1[3], a2[2], a3[2], a4 [1]}. Two pairs of ac­ tivities that might be selected for ordering are< a2 , a4 > or < a2 , a1 >. In the case of < a2, a1 > the combined requirement exceeds Ck and hence any feasible solution must have a2 and a1 reciprocally ordered. Alternatively, an ordering of the pair < a2, a1 > may or may not bees­ sential to leveling the conflict . One observed shortcom­ ing of previous profile-based approaches to cumulative scheduling has been their tendency to post unnecessary ordering constraints, following from the use of conflict selection and resolution heuristics that rely strictly on pairwise analysis of competing activities [Cesta et al., 1998a].

Conflicts are Minimal Critical Sets of Activities. An alternative approach to conflict analysis that can overcome this problem has been proposed in [Laborie and Ghallab, 1995]. Under this scheme, an activity "intersection graph" is constructed and systematically searched for particular cliques. Such a clique is called a Minimal Critical Set (Mcs). It specifies a set of ac­ tivities that simultaneously require a resource rk with a combined capacity requirement > Ck , such that the com­ bined requirement of any subset is ::; Ck. The important advantage of isolating Mess is that a single precedence relation between any pair of activities in the MCS eliminates the resource conflict .

Unfortunately, the exponential nature of the intersec­ tion graph search prohibits use of this basic approach on scheduling problems of any interesting size. In [Cesta et al., 1998b], it is shown that much of the advantage of this type of global conflict analysis can be retained by using an approximate procedure for computing MCSs. But the pragmatic cost of recomputing MCSs across all resources at each iteration of the CSP resolution pro­ cedure nonetheless remains high and significantly limits scalability.

In ESA, we achieve an even better computational tradeoff by instead integrating the use of MCS analysis into a profile-based scheduling framework. On each it­ eration of the search, we first compute contention peaks (which is quadratic in the number of activities) to isolate those areas of the solution where conflicts (i.e., Mess) should be computed. Next we generate a set of Mess for each peak. (These two steps are embedded respec­ tively in the ResourceFeasible(ESTsol) predicate and ExistUnsolvableConflict function of lines 4 and 7 in the algorithm description of Figure 1.) The number of Mess contained in a given peak can still be quite large (in the worst case C~'2 1 )), and, accordingly, ESA also uti­ lizes an approximate (heuristic) scheme for computing MCSS.

Computation of Critical Minimal Sets. Two heuristic sampling schemes for computing the set of Mess associated with a given contention peak P are evaluated in this paper: linear sampling and quadratic sampling. In both cases, the activities j E P are first sorted in or­ der of decreasing size of their capacity requirements (i.e. largest first), to promote detection of the "most critical" MCSs. The two schemes are summarized as follows :

• Linear sampling. Under this scheme, a queue Q is used to select an MCS in P. Activities j E P are se­ quentially considered (in sorted order) and inserted in Q until the sum of the resource requirements ex­ ceed the resource capacity. At this point, the set Q (the current Mcs) is collected in a list of Mess and the first element from Q is removed. The previous steps are iterated and Mess are collected until there are no uninserted activities in P .
• Quadratic sampling. This scheme can be seen as an extension of linear sampling in which the second step is expanded as follows. Once the current MCS has been collected, instead of immediately removing the first element from Q, a forward search through the remaining uninserted activities in P is first per­ formed to also collect all MCSs that can obtained by dropping the last item placed in Q and substituting with single subsequent activities in P until an MCS is still composed.

Consider again the peak from the previous example {al[3], a2[2], a3[2], a4 [1]} and resource rk with ck = 4. Although the peak contains three Mess linear sampling collects only two: {al[3], a2[2]} and {a2[2], a3[2], a4 [1]}. Quadratic sampling, on the other hand, would also find the third: {a1[3], a3[2]} .

Conflict Removal. Lines 10-12 of the ESA algorithm in Figure 1 remove an MCS from the current solution. The basic steps involve selecting an MCS from the current conflict set (Line 10), selecting a precedence constraint that resolves the selected MCS (Line 11), and posting the constraint in ESTsol to perform temporal constraint propagation (Line 12) .

The heuristics that govern both conflict selection and conflict resolution in ESA are based directly on least commitment concepts previously utilized for other prob­ lems with maximum time lags (e.g., [Cheng and Smith, 1994; Laborie and Ghallab, 1995]). Candidate Mess are ordered according to the temporal flexibility they con­ tain (a function of the degree to which constituent ac­ tivities can be reciprocally shifted in time). The less flexibility a MCS has, the more critical it is to resolve first . The greater the flexibility that is retained after posting a precedence constraint that resolves a MCS, the more desirable. it is to post that constraint.

To quantify the notion of temporal flexibility, the heuristic estimator K suggested in [Laborie and Ghal­ lab, 1995] is used. Given a candidate MCS and a set {pc1 ... pck} of precedence constraints that could be posted between pairs of activities in the MCS, K(Mcs) is defined as follows:

where commit(pc;) ranges from 0 to 1 and estimates the loss in temporal flexibility as a result of posting con­ straint pc; , and PCmin is the precedence constraint with the minimum value of commit(pc).

Note that K(Mcs) takes on its highest value of 1 in those cases where only one specific precedence con­ straint can be feasibly posted to resolve the conflict . In general, the closer an MCS is to being unresolvable, the higher the value of K(Mcs). The conflict selection heuristic (SelectConflict) chooses the MCS with the highest K value, and the conflict resolution heuristic ( SelectPrecedence) simply chooses PCmin.

3.3 Randomizing ESA ·

The ESA resolution procedure, as defined above, is a de­ terministic (partial) solution procedure with no recourse in the event that an unresolvable conflict is encountered. To provide a capability for expanding the search in such cases without incurring the combinatorial overhead of a conventional backtracking search, we define a random counterpart of our conflict selection heuristic (in the style of [Oddi and Smith, 1997]) and embed the resulting "Random-ESA" procedure within an iterative sampling search framework. Specifically, the heuristic employed by SelectConflict is modified as follows. We define an acceptance band {3 and consider as equivalent the set of MCSs for which Kmax(1 - {3) ~ K(Mcs) ~ Kmax· The conflict to be resolved next is randomly selected from this set, resulting in a non-deterministic yet heuristically­ biased choice.

Figure 2 depicts the larger iterative sampling algo­ rithm. It is designed simply to invoke the random-ESA

mresESA(Problem, MaxRestart, Horizon)

1. Sbe·t f-- EmptySolution
2. Sol f-- EmptySolution I* MK(EmptySolution)=+oo *I
3. Counter f-- 1
4. While Counter < MaxRestart and M-K(Sol) > mko do
5. Sol f-- ESA(Problem, Horizon)
6. if MK(Sol) < MK(Sbe·t)
7. then Sbe·t f-- Sol
8. Counter f-- Counter + 1
9. end-while
10. return(Sbe·t)
11. end

Figure 2: The Restarting ESA Procedure

resolution procedure a fixed number (MaxRestart) of times, rather than predicating any restarts on a failure to produce a feasible solution. Given that the broader objective in this paper is makespan minimization, each restart provides a new opportunity to produce a different feasible solution with lower makespan.

4 An Optimization Procedure

Though the restarting procedure just described does in fact retain the smallest makespan solution generated across calls to mresESA, its principal role is to produce a feasible solution relative to a given upper-bound hori­ zon. In this section, we define an RCPSP /max opti­ mization procedure based on use of this feasible solution generator, and relate it to previous OR approaches to RCPSP/max.

4.1 The ISES Algorithm

Similar to other CSP procedures for makespan minimiza­ tion (e.g., [Cheng and Smith, 1997]), we adopt a multi­ pass approach; the feasible solution generator is repeat­ edly applied to solve problems with increasingly smaller temporal horizons, until it is no longer possible to find a feasible solution or until a lower-bound solution is found.

Figure 3 shows the specific multi-pass version of the base ESA procedure we have defined, called ISES (It­ erative Sampling Earliest Solutions). ISES is composed of two basic steps. First, a feasible solution is found by invoking mresESA with a horizon value (MaxH) much greater than the lower bound mk0 . (mko is the initial "in­ finite capacity" solution to Problem) . Successive calls are then made to mresESA each time substituting the new best makespan found on the previous call as the new problem horizon. The iteration stops when either (1) a call to mresESA returns an empty solution, (2) a lower bound solution is obtained , or (3) a solution is returned which does not improve the previous best .

4.2 Comparison to OR Approaches

As previously noted, the work of [Bartusch et al. , 1988] investigates the mathematical properties of the problem and similarly characterizes the solution space using the temporal constraints. The notion of forbidden sets is introduced to represent resource conflicts, equivalent to ISES(Problem, MaxRestart , MaxH)

1. Sbest +- EmptySolution I* find a first feasible solution *I
2. Sol +- mresESA(Problem, MaxRestart, MaxH)
3. if Sol # EmptySolution then I* improve the current makespan *I
4. repeat
5. Sbest +- Sol
6. Sol+- mresESA(Problem, MaxRestart, MK(Sbest ))
7. until mko < MK(Sol) < MK(Sbest)
8. return(Sbest)
9. end

Figure 3: The ISES Optimization Algorithm

our definition of contention peaks. The paper also de­ fines a concept similar to MCS (called reduced forbidden set). This is used to sketch a systematic B&B procedure which similarly starts from an infinite capacity solution and extends the set of precedence relations in the prob­ lem. Unfortunately the computational analysis is quite limited. Only small instances are mentioned and this approach has not influenced later OR computational ap­ proaches to RCPSP /max. ISES can be seen as an ap­ proximation algorithm based on the same ideas (even if 1t has evolved from other origins) .

More recent B&B approaches have retained the idea of extending a time-feasible solution by adding precedence relations, but analyze the current solution differently. In [De Reyck and Herroelen, 1998] and [Schwindt, 1998], peaks are considered in increasing chronological time or­ der and, for each of them, a set of "minimal delaying activities" are detected for resolving conflicts. Alterna­ tively, ESA does not depend on the chronological time order, but opportunistically acts on the more constrained part of the solution. Other B&B algorithms work differ­ ently. For example [Mohring et al. , 1998] solves resource conflicts by increasing release dates (minimum time lags relative to beginning of the project) for certain activi­ ties instead of introducing precedence relations. A very recent proposal [Dorndorf et al. , 1998] obtained strong results using a combination of techniques: it couples a set of temporal and resource constraint propagation rules with a binary branching schema that exploits particular properties of the current partial solution to successively fix and/or delay the start-times of various activities.

Approximate approaches are also defined in the OR literature. One heuristic analysis [Franck and Neumann, 1998] very recently obtained very good results on the RCPSP /max benchmark problems. Despite being clas­ sified as a "priority rules" approach, this work uses a two step method: (a) a sophisticated decomposition analysis is performed to identify "critical sub-components" which can be scheduled independently, and (b) the scheduled sub-components (partial schedules) are integrated into one using a set of priority rules. Note that the first step uses properties due to the presence of maximum time lags. With respect to ISES this approach is determinis­ tic and relies on a quite different analysis of the problem.

5 Experimental Evaluation

Our experimental evaluation of ISES focuses on two sets of reference problems taken from the RCPSP /max prob­ lem repository 2 :

• Problem set A. This is the benchmark problem set described in [Kolisch et al., 1998]. It consists of three sets of 270 problems each, named J10, J20 and J30 , with problems of 10, 20 and 30 activities respectively and 5 resources. The only known re­ sults for this problem set to date have been obtained using the B&B procedure of [Schwindt, 1998]
• Problem set B. This is the benchmark problem set in­ troduced in [Schwindt, 1998] and used by the recent B&B approaches mentioned in Section 4.2. It con­ sists of 1080 problems with 100 activities and 5 re­ sources, of which 1059 are feasible and the rest are provably infeasible. For this set, lower bounds are known for each problem [Heilmann and Schwindt , 1997], providing a common reference point for mea­ suring deviation from optimal solutions.

Both above problem sets were generated by PRO­ GEN/max, a flexible random networks generator [Schwindt, 1996] that allows generation of project scheduling problems of varying structure, constrained­ ness and difficulty. However, due to differences in the generation parameters used in each case, there are im­ portant differences in the characteristics of the problems in each set. The parameter settings used to generate Problem Set A are closer than Problem Set B's to the settings which produce the "hardest possible" problems [Franck and Neumann, 1998]. In particular, the prob­ lems in Set A exhibit higher levels of resource contention (i .e., higher contention peaks) than those in Set B, along with increased parallelism in project activities (i .e., in­ creased sequencing flexibiliy). Given these properties , we can expect deeper search trees (i.e., a larger search space) in solving problems from Set A than for prob­ lems in Set B, since a greater number of ordering deci­ sions are needed to build up a feasible solution. Hence, even though Problem Set B contains larger (100 activity) problems, the problems in Problem Set A are actually very challenging.

5.1 Experimental Design.

Results are obtained with ISES on Problem Sets A and B using both linear and quadratic MCS sampling schemes. For all experiments, the randomization factor f3 in MCS selection is set to 0.1, so all Mess within the 10% of the maximum ranked are considered as equivalent . The number of restarts of the resolution procedure at a given horizon (MaxRestart) is set to 10 and 30 for problem set A, and to 10 for problem set B. The maximum horizon MaxH is set to 5 x mko.

All algorithms compared to ISES below have been im­ plemented in C++ and run on a Pentium 200 with an im­ posed time limit of 100 seconds per problem. Our current implementation of JSES is in Allegro Common Lisp and the reported results are obtained on a SUN UltraSparc 30 (266MHz). The C++ and Lisp implementations are not directly comparable, but we have nonetheless im­ posed the same 100 second time limit. For problem set B we also compute the performance of ISES for 300 and 500 second limits to better understand the behavior of the algorithm.

2 Available at ftp://ftp.vior.uni-karlsruhe.de/ pub/ProGen-max/pspmaxlib/

Given the non-deterministic nature of ISES each prob­ lem is solved multiple times using different random seeds (similar to [Nuijten and Le Pape, 1998] which also evalu­ ates a random restart algorithm). We report two results: (1) the best result (ISESbe·t(n)), obtained using the best result on any single problem over the n different runs, and (2) the average result (ISESavg(n j), obtained using the average result on each problem over its n runs.

5.2 Problem Set A

Table 1 gives overall performance results on the J10, J20 and J30 problem classes of Problem Set A for the best performing ISES configuration (MaxRestart=30, quadratic sampling) and the B&B approach of [Schwindt, 1998] (labeled B&Bsgs). The first column, ( N opt) , is interpreted differently in the case of each algo­ rithm: for B&Bs98 , it indicates the number of problems solved to optimality; for ISES, it indicates the number of problems for which the same solution as B&Bsgs was obtained. The second column, Nfea·, gives the number of problems feasibility solved by both approaches. The last column, N;mpr, makes sense only for ISES, indicat­ ing the number of problems for which ISES finds better solutions than B&Bs98. Average ISES solution times on J10, J20, J30 problems were 0.87, 5.76 and 17.97 seconds respectively.

We can observe the following:

• On the smaller J10 and J20 problems the exact B&Bs98 procedure dominates ISES, but on both the sets ISES finds all feasible solutions.
• on J30 JSES finds 2 feasible solutions (on all runs) that elude B&Bs9s and (on average) improves on 20 solutions produced by B&Bs9B·
• as problem size increases, from J10 to J30, ISES finds lower-makespan solutions than B&Bs98 on in­ creasing numbers of problems.

Table 2 shows the relative deviation of the makespans produced by ISES from those produced by B&B for both ISESbe· t(n) and ISESavg(n) (with same configuration as above). We can see that :

• the average deviation in solution quality across all problems is less that 1.6%.
• the differential in solution quality progressively decreases as problem size is increased.

In Table 3 we indicate the effects on solution quality of varying the MCS sampling strategy and the number of restarts on the J30 problem subset . It can be seen that increasing the number of restarts always has a positive effect, and that the more accurate (quadratic) sampling produces a significant improvement .

On balance, the comparative results on Problem Set A suggest that ISES provides a scalable alternative to exact B&B solution procedures on "hard" RCPSP /max prob­ lems. It is worth mentioning that in [Franck and Neu­ mann, 1998] results with similar size problems (number of activities in the range {10,15,20} with similar param­ eters for PROGEN/max) are reported, and the heuristic approach proposed there compared quite badly with re­ spect to B&B.

5.3 Problem Set B

Table 4 reports performance results for ISES on Problem set B using the same metrics originally used in the B&B study of [Schwindt, 1998]. These include:

• ~LB% - the average relative deviation from the lower bound computed by using [Heilmann and Schwindt, 1997];
• Nopt% - the percentage of optimal solutions found (i .e., solutions that equal the best known lower bound or are proved optimal by a B&B) ;
• Nfea·% - the percentage of problems solved to feasibility.

We compare the performance of JSES (MaxRestart=10, linear sampling) with all recently reported branch and bound approaches for RCPSP /max, including those of [De Reyck and Herroelen, 1998] (labeled B&BdRH), [Mohring et al. , 1998] (labeled B&BM98 ), [Schwindt ,

1998] (labeled B&Bs9s), and [Dorndorf et al., 1998] (la­ beled B&Bv9s). We also include the above mentioned heuristic procedure of [Franck and Neumann, 1998] (la­ beled P Rlp!J 98 ). In this case, no decomposition strat­ egy /priority rule pair was found to outperform all oth­ ers on all problems, so we include in Table 4 the results obtained by using the best performing decomposition scheme and, for each problem, taking the best solution found by 10 priority rules.

Several observations follow from Table 4:

• ISES is one of three approaches that is able to find all feasible solutions (98.06%) within a 100 second time bound. In this regard, ISES outperforms P RFN98, previously the best heuristic procedure known for RCPSP /max. In fact, ISES also appears to be more robust than P RFN98 ; across all 15 runs performed with ISES, no more than 3 feasible solutions were ever missed on a single run.
• all B&B approaches except B&BdRH find higher percentages of optimal solutions than ISES. How­ ever, with regard to deviation from lower bound solutions ilLs% ISES ranks third behind B&BD9s and B&Bs9s, and is in fact fairly comparable to B&Bs9s with a 300 second time limit. (Note that ilLs% is influenced by the number of feasible so­ lutions found; solving the more difficult problems typically increases the deviation [Dorndorf et al., 1998]) .
• Contrasting the performance of ISES at different time limits, significant improvement is obtained in increasing the time limit from 100 to 300 seconds but the further increase to 500 seconds achieves only limited further improvement.

The clearly dominating procedure on Problem Set B is B&BD9s of [Dorndorf et al., 1998]. It is interesting to note that this approach exploits resource constraint propagation rules that could be straightforwardly added to ISES. We are currently investigating this possibility.

The average solution times obtained for ISES at each different time limit give some additional insight into its behavior on this problem set , and are as follows: 43 .91 seconds (100 second limit) , 72.21 seconds (300 second limit) and 84.79 seconds (500 second limit). The fact that average solution times rise fairly slowly in propor­ tion to increases in the time limit indicates that there are only a relatively small percentage of problems that cannot be efficiently solved. For example, in examining particular runs of ISES, the percentage of solvable prob­ lems that require over 100 seconds for solution is seen to be 25%.

Finally, Table 5 indicates the performance effect of in­ corporating the more-comprehensive quadratic MCS sam­ pling strategy with a 500 second time bound. In this case, the average solution time increases just slightly to 91.49 seconds, and as Table 5 shows, there is virtually no improvement in solution quality. This ineffectiveness can also be explained by recalling the prior discussion of the characteristics of Problem Set B. The level of resource contention in these problems is only small to moderate, resulting in contention peaks that are relatively smooth and contain few Mess. Accordingly, there are few Mess that are not found by linear sampling and a more accu­ rate strategy adds very little.

6 Conclusions

This paper investigates the use of an iterative sampling procedure to solve RCPSP /max, a complex optimiza­ tion problem. The ISES procedure uses a combination of constraint-guided greedy search and randomization. The greedy search procedure utilizes analysis of "min­ imal conflict sets" (Mess) to identify where additional ordering constraints are required to avoid resource con­ tention. MCS analysis is integrated with least commit­ ment principles related to retaining temporal flexibility to provide heuristics for focusing the search. Randomiza­ tion is introduced in a way that incorporates the bias of these greedy search heuristics. This provides a basis for smoothing the decisions of the deterministic algorithm and for broadening the search to include heursitically equivalent search paths in the space, thus enhancing the probability of finding better quality solutions.

A further contribution is represented by the approx­ imate computation of Mess, which avoids the basic ex­ ponential computation and attempts to first select the most critical minimal conflicts at a low polynomial cost .

ISES has been compared with the best existing ap­ proaches to RCPSP /max. It outperforms several sys­ tematic and heuristic approaches on different reference problem sets. In particular , ISES is shown to perform quite well in situations where, due to problem character­ istics such heavy resource contention, the search space is quite large and becomes a serious obstacle for systematic approaches. In this case, our non-systematic random approach demonstrates an advantageous trend in compar­ ison to the best known systematic algorithm (in terms of both the number and the quality of the solutions pro­ vided) as problem size is increased. It is worth noting that our method relies mainly on its composite search strategy and heuristics, rather than on a set of propa­ gation rules for early pruning of the search space. The addition of the latter could be an interesting direction for future research.

Acknowledgments

Authors would like to thank Dr. Christoph Schwindt for creating the repository that made possible the ex­ perimental comparison described in this work and for giving prompt clarifications on its use. We also thank the various authors who have made available their up­ dated unpublished works on this topic. Amedeo Cesta and Angelo Oddi 's work is supported by Italian Space Agency, by CNR Committee 12 on Information Tech­ nology (Project SCI*SIA), and CNR Committee 4 on Biology and Medicine. Stephen F. Smith's work has been sponsored in part by the National Aeronautics and Space Administration under contract NCC 2-976, by the US Department of Defense Advanced Research Projects Agency under contract F30602-97-20227, and by the CMU Robotics Institute.