Proactive Algorithms for Scheduling with Probabilistic Durations J. Christopher Beck Nic Wilson Department of Mechanical & Cork Constraint Computation Centre Industrial Engineering Department of Computer Science University of Toronto, Canada University College Cork, Ireland jcb@mie.utoronto.ca n.wilson@4c.ucc.ie Abstract probabilistic makespan of solutions. (iii) It is demonstrated that the method introduced by Beck & Wilson for the in- Proactive scheduling seeks to generate high quality corporation of uncertainty in deterministic problems can in- solutions despite execution time uncertainty. Build- crease the correlation between deterministic and probabilis- ing on work in [Beck and Wilson, 2004], we con- tic makespan, providing an explanation for its strong perfor- duct an empirical study of a number of algorithms mance. for the job shop scheduling problem with proba- In the next section we briefly review previous work. The bilistic durations. The main contributions of this six search algorithms investigated in this paper are defined in paper are: the introduction and empirical analy- Section 3 and Section 4 presents our experiments and results. sis of a novel constraint-based search technique In Section 5, we present our conclusions. that can be applied beyond probabilistic scheduling problems, the introduction and empirical analysis 2 Background of a number of deterministic filtering algorithms for The job shop scheduling problem (JSP) consists of a set A probabilistic job shop scheduling, and the identifi- of activities each with a positive integer-valued duration, di . cation of a number of problem characteristics that A is partitioned into jobs, and with each job is associated a contribute to algorithm performance. total ordering on that set of activities. Each activity speci- fies a resource on which it must execute without interruption. 1 Introduction No activities that require the same resource can overlap in Classical models of scheduling assume all information is their execution. We represent this formally by a partition of known and static. When faced with uncertainty, proactive A into resource sets. A solution consists of a total ordering scheduling techniques seek to incorporate models of the un- on each resource set such that the union of the resource and certainty in the off-line problem solving and to build solu- job orderings is an acyclic relation on A. The makespan of tions that can achieve a satisfactory level of performance at a solution is the difference between the minimum start time execution time. [Beck and Wilson, 2004] addressed the prob- and the maximum end time of all activities. Finding a solu- lem of job shop scheduling with probabilistic durations with tion with minimum makespan is NP-hard [Garey and John- two styles of algorithm both using Monte Carlo simulation to son, 1979]. An independent probabilistic job shop schedul- evaluate the probabilistic makespan of solutions. This paper ing problem is a JSP where the duration di associated with builds on that work, making the following contributions: (i) an activity Ai A is a positive integer-valued random vari- A novel constraint-based search technique is introduced that able. These random variables are fully independent. di has performs a series of complete branch-and-bound searches on expected value µi = E[di ] and variance i = Var[di ]. 2 highly constrained problem models. The models are gradu- The makespan make(s) of solution s is therefore also a ran- ally relaxed with the cost of the best solution model found in dom variable. We fix a degree of confidence p, e.g., we set the previous searches being used as an upper bound. Exper- p = 0.95 in the experiments. The minimum probabilistic imental results show that the algorithm performs as well as makespan, D(s), of a solution s is the smallest value D such the existing branch-and-bound style of search on small prob- that the probability that all jobs will finish before D is at least lems and significantly out-performs it on larger problems. (ii) p. That is, D(s) = min{D : Pr(make(s) D) p}. An A number of novel deterministic filtering algorithms are pre- optimal probabilistic makespan is the minimum D(s) over all sented. On larger problems such algorithms out-perform the solutions s. other algorithms tested. Their performance is affected by the Beck & Wilson introduce an analytical model and develop following two factors: the quality of the deterministic solu- two main results. First, it is demonstrated that Monte Carlo tions found and the correlation between the deterministic and simulation can be used to find the probabilistic makespan for a solution and to find a lower bound on the probabilistic This material is based upon works supported by the Science makespan of a partial solution. Second, it is shown that a de- Foundation Ireland under Grant No. 00/PI.1/C075 and by ILOG, terministic JSP instance can be constructed from a probabilis- SA. B&B-DQ-L(): tic JSP instance by setting the duration di of each activity to Returns the solution with lowest probabilistic makespan µi +q i and that, for the appropriate choice of non-negative q , the optimal makespan of the deterministic instance is a lower (s , D ) findFirstB&BSimLeaves(, 0) 1 bound on the optimal probabilistic makespan of the corre- q q0 2 sponding probabilistic JSP. Three algorithms are defined: a while q 0 AND not timed-out do 3 branch-and-bound approach where Monte Carlo simulation is (s, D) findOptB&BSimLeaves(D , q ) 4 used at each node to find a lower bound (at internal nodes) or if s = N I L then 5 an upper bound (at a leaf node) on the probabilistic makespan, s s; D D 6 and two deterministic filtering algorithm consisting of using end either constraint-based search or tabu search to find a series q q - qdec 7 of increasingly good deterministic solutions, each of which is end simulated. Empirical results indicated that the first algorithm return s 8 was able to find optimal solutions only for very small prob- Algorithm 1: B&B-DQ-L lems, that for medium-sized problems the constraint-based filtering algorithm found the best solutions, and for the largest problems the tabu-based filtering algorithm performed best. found by any point in the overall search is used, as in B&B-N, Choosing q > 0 led to stronger performance of the filter- as an upper bound on subsequent search. ing algorithms. No empirically founded explanations were Algorithm 1 presents pseudocode for the basic algorithm. provided to explain the differences in problem solving per- We make use of two functions not defined using pseu- formance. docode: findFirstB&BSimLeaves(c, q ) creates a JSP with activity durations defined based on the q value and con- 3 Algorithms for Probabilistic JSP ducts a branch-and-bound search where Monte Carlo sim- ulation is used for each leaf node and standard constraint In this section, we describe six algorithms for solving the propagation is used at interior nodes. The first solution probabilistic job shop scheduling problem. that is found whose probabilistic makespan is less than c is returned. findOptB&BSimLeaves(c, q ) does the same as 3.1 Approximately Complete Branch-and-Bound findFirstB&BSimLeaves(c, q ) except the solution with lowest We implemented a branch-and-bound algorithm identical to probabilistic makespan is returned rather than the first one. that of Beck & Wilson except that we use stronger heuristics If no solution is found, a NIL value is returned. Unless the that make decisions on the sequence of activities in each re- q value is low enough that the deterministic makespan is a source set (see Section 3.5). We refer to this algorithm as the lower bound on the probabilistic makespan, this function does B&B-N as it performs Branch-and-Bound with simulation at not necessarily return the globally optimal solution. We find a each N ode. starting solution with q = 0 to serve as an initial upper bound on the probabilistic makespan. In practice, B&B-DQ-L is run 3.2 Iterative Descending Bound Search with a maximum CPU time. If q = 0 is reached within the By setting activity durations based on a q value that ensures a time limit, this algorithm is approximately complete. lower bound on the probabilistic makespan, we can use stan- We refer to this algorithm as B&B-DQ-L as it does a series dard constraint propagation on the deterministic durations to of Branch-and-Bound searches with Descending Q values and implicitly calculate a lower bound at each internal node. At with simulation is used at the Leaves of the tree. each leaf node, simulation is used as in B&B-N to find the 3.3 Branch-and-Bound Filtering Algorithms probabilistic makespan. Rather than parameterize the algo- rithm with a fixed q value, we perform repeated tree searches Preliminary experiments with the branch-and-bound filtering with a descending q value. Starting with a high q value, algorithm presented by Beck & Wilson showed that a signifi- we begin a tree search. When the first leaf, e, is reached, cant amount of simulation was being done early in the search simulation is used to find D(se ). It is likely that Dq (se ), when the upper bound on the deterministic makespan was rel- the minimum makespan of se in the corresponding deter- atively high. Such solutions would seem to have little chance ministic problem, will be larger than D(se ). Since we en- of being the optimal probabilistic solution as the deterministic force Dq (se ) D(se ), estimating D(se ) through simulation solution is very poor. We present two constraint-based filter- causes the search to backtrack to a interior node, i, very high ing algorithms that seek to avoid these wasted simulations. in the tree. At node i, Dq (Si ) D(se ): Si is the set of solutions in the subtree below node i and Dq (Si ) is a lower Branch-and-Bound Timed Better Solution A simple bound on the deterministic makespan of those solutions based method is to spend a fixed amount of CPU time, tinitial to find on standard constraint propagation. With high q values, we a solution, s , with a low deterministic makespan Dinitial us- commonly observe that there are very few nodes that meet ing a fixed q value and constraint-based search. Then search this criterion and the search space is quickly exhausted. We can be restarted using the same q value and using Dinitial as then decrement the q value (e.g., by 0.05) and start a new tree an upper bound on the deterministic makespan. Whenever a search. Eventually, and often very quickly, we reach a q value solution, s, is found such that Dq (s) Dinitial , a simulation such that there exists a full solution where Dq (se ) D(se ). is run to evaluate the probabilistic makespan. The solution The probabilistic makespan of the best solution that has been B&B-I-BS(q ): B&B-TBS(q): Returns the solution with smallest probabilistic makespan Returns the solution with lowest probabilistic makespan (s , Dinitial ) findOptB&B(, q , t0 - 1) (s , Dinitial ) findOptB&B(, q , tinitial ) 1 1 D simulate(s ) D 2 2 while termination criteria unmet AND not timed-out do i0 3 3 while not timed-out do (s, D) findNextB&B(Dinitial , q , tremaining ) 4 4 while termination criteria unmet do D simulate(s) 5 5 if D < D then (s, Dq ) findNextB&B( 6 6 Dinitial × (1 + i/100), q , tremaining ) s s; D D e 7 nd D simulate(s) 7 end if D < D then 8 return s s s; D D 8 9 end Algorithm 2: B&B-TBS end ii+1 10 end with the lowest probabilistic makespan is returned when ei- return s 11 ther the entire tree has been searched or when the maximum allowed CPU time has expired. Algorithm 2 contains pseu- Algorithm 3: B&B-I-BS docode for this approach. As above, we make use of a number of functions not de- ulated. However, i would have to grow unreasonably large fined with pseudocode: findOptB&B(c, q , t) creates a JSP and therefore we treat this algorithm as, practically, incom- with activity durations defined based on q and conducts a de- plete. We refer to this algorithm as B&B-I-BS for Branch- terministic branch-and-bound search for up to t CPU seconds and-Bound-I terative-Best Solution. using c as an upper bound on the makespan. When the search tree is exhausted or the time-limit is reached, the best solution 3.4 Local Search Filtering Algorithms found, together with its makespan, are returned. No simula- We also experiment with two local search filtering algorithms tion is done. findNextB&B(c, q , t) produces a sequence of analogous to the constraint-based algorithms above except solutions (one solution each time it is called) whose deter- that tabu search is used in place of constraint-based search. ministic makespan is less than or equal to c. The problem is defined using the q value and t is the CPU time limit. The Tabu Timed Better Solution For a fixed q and for a fixed solutions produced are the leaves of the B&B search tree in CPU time, tinitial , a solution with the lowest determinis- the order encountered by the algorithm. The c value does not tic makespan, Dinitial , possible is sought. Search is then change. Given enough CPU time, the algorithm will evalu- restarted and whenever a solution, s, is found that has a de- ate the probabilistic makespan of all solutions whose deter- terministic makespan Dq (s) Dinitial , simulation is used ministic makespan is less than or equal to Dinitial . Finally, to evaluate the probabilistic makespan. The solution with simulate(s) runs Monte Carlo simulation on solution s and the lowest probabilistic makespan is returned. The pseu- the probabilistic makespan is returned. docode for Tabu-TBS is the same as that for B&B-TBS The algorithm is called B&B-TBS for Branch-and-Bound (Algorithm 2) with the following changes. The function T imed Better Solution. The algorithm is not complete, as findNextTabu(c, q , t) replaces findNextB&B(c, q , t); it pro- there is no guarantee that the optimal probabilistic solution duces a sequence of solutions whose deterministic makespan will have a deterministic makespan less than Dinitial . is less than c. The findBestTabu(c, q , t) function replaces findOptB&B(c, q , t); tabu search is run for up to t CPU sec- onds and the solution with the lowest deterministic makespan Branch-and-Bound Iterative Best Solution A more ex- that is less than c is returned. We call this algorithm Tabu-TBS treme filtering algorithm first finds an optimal deterministic for Tabu-T imed Better Solution. solution and uses it as a filter for choosing the solutions to simulate. Using a fixed q value, a solution with an optimal deterministic makespan, Dq , is found and simulated. Then Tabu Iterative Best Solution The core tabu search imple- we execute a series of iterations beginning with i = 0. For mentation does not necessarily use the entire CPU time. We each iteration, all solutions, se , with deterministic makespan can therefore create an iterative tabu-based solver for the Dq (se ) Dq × (1 + i/100) are simulated and the one with probabilistic JSP similar to B&B-I-BS. In the first phase, the lowest probabilistic makespan is returned. If an opti- using the overall time limit less one second, tabu search is mal deterministic solution cannot be found within the CPU used to find a good deterministic solution, based on a fixed q time limit, the best deterministic solution found is simulated value. That solution is then simulated. Any remaining time and returned (i.e., only one simulation is done). Algorithm 3 is spent generating solutions with a deterministic makespan presents the pseudocode. within a fixed percentage of the initial solution's determin- istic makespan. As with B&B-I-BS, iterations are run with The algorithm is theoretically complete. When i is large increasing i value starting with i = 0. In each iteration, solu- enough that the cost bound is greater than the deterministic tions found by the tabu search whose deterministic makespan makespan of all activity permutations, they will all be sim- are within 1 + i/100 of the initial deterministic makespan q0 q1 q2 A q3 verageAi i are simulated. The solution with the lowest probabilistic 2 0 q1 +q3 B B Average Ai i makespan is returned. The algorithm is termed Tabu-I-BS 2 n 2n for Tabu-I terative-Best Search. The pseudocode for this al- Table 1: The q -values used, following Beck & Wilson. n is gorithm is the same as that for B&B-I-BS (Algorithm 3) with the number of jobs and B = 1.645. the same substitutions that were made for Tabu-TBS. 3.5 Core Algorithm Details makespan found by algorithm a on l over 10 runs, Dlb (l) is The branch-and-bound algorithms described use texture- the lower bound on the probabilistic makespan for l. For all based heuristics [Beck and Fox, 2000] to decide on the the problems except 20 × 20, the Dlb is found by solving the de- pair of activities to sequence and which sequence to try first. terministic problems to optimality using the q1 durations (see When constraint propagation is used (i.e., all B&B algorithms Section 3 of [Beck and Wilson, 2004]). For the 20 × 20 prob- except B&B-N), we use temporal propagation, timetables lems, the optimal solutions could not be found and so the Dlb [Le Pape et al., 1994], edge-finder [Nuijten, 1994], and the values represent the best deterministic solutions found. These balance constraint [Laborie, 2003]. values, therefore, are not a true lower bound. The tabu search is the same one used by Beck & Wilson: The hardware used for the experiments is a 1.8GHz Pen- the TSAB algorithm of [Nowicki and Smutnicki, 1996]. tium 4 with 512 M of main memory running Linux RedHat 9. All algorithms were implemented using ILOG Scheduler 5.3. 4 Empirical Investigations Our empirical investigations aim to evaluate and investigate 4.2 Results the performance of the algorithms. In particular, we are inter- Table 2 presents the results of our experiment. Each cell is ested in algorithm scaling with problem size and uncertainty the mean over 10 independent runs of 10 problems. The ob- level and with the usefulness of representing uncertainty in- served mean standard deviations for each cell are small: the formation using q values. maximum over all cells is less than 10.3% of the correspond- 4.1 Experimental Details ing mean makespan, while the mean over all cells is less than 0.8%. We did not observe a large difference among the q val- We use four sets of probabilistic JSPs of size {4×4, 6×6, 10× ues provided q > 0 and therefore present the results for q2 . 10, 20 × 20} with three uncertainty levels uj {0.1, 0.5, 1}. A deterministic problem is generated using an existing gen- erator [Watson et al., 2002] with integer durations drawn uni- Algorithms Problem Unc. B&B Complete B&B Heuristic tabu formly from the interval [1, 99]. Three probabilistic instances Size Level N DQ-L TBS I-BS TBS I-BS 1.023* 1.023 0.1 1.027* 1.026 1.026 1.027 are then produced by setting the mean durations µi to be the 1.046 0.5 1.060* 1.049* 1.064 1.059 1.061 4×4 deterministic durations and by uniformly drawing the stan- 1.128 1 1.151* 1.129 1.154 1.149 1.150 dard deviation i from the interval [0, uj µi ]. The distribution 1.021 0.1 1.034 1.022 1.022 1.025 1.023 1.073 0.5 1.113 1.083 1.077 1.089 1.074 6×6 of each duration is approximately normal. For each problem 1.168 1 1.226 1.170 1.178 1.174 1.182 size, we generate 10 deterministic problems which are trans- 1.024 1.024 0.1 1.185 1.028 1.035 1.028 1.101 1.101 0.5 1.241 1.115 1.121 1.112 formed into 30 probabilistic instances. 10 × 10 1.215 1.215 1 1.346 1.234 1.244 1.223 Given the stochastic nature of the simulation and the tabu 1.027 0.1 1.256 1.142 1.077 1.071 1.029 1.136 search algorithm, each algorithm is run 10 times on each 0.5 1.326 1.233 1.177 1.181 1.137 20 × 20 1.297 1 1.482 1.388 1.334 1.338 1.307 problem instance with different random seeds. Each run has a time limit of 600 CPU seconds. Each Monte Carlo simulation Table 2: The mean normalized probabilistic makespans for uses 1000 trials. For B&B-TBS and Tabu-TBS, tinitial is 60 each algorithm. `*' indicates a set of runs for which we have, CPU seconds. with high confidence, found close-to-optimal makespans. `' For the heuristic techniques, a deterministic duration is as- indicates problem sets for which normalization was done with signed to each of the activities based on the q value. We ex- approximate lower bounds. The lowest MNPM found for periment with the same four q values used by Beck & Wilson each problem set are shown in bold. as displayed in Table 1. The B&B-DQ-L algorithm requires an initial value of q , q0 , and a decrement, qdec . For all except For the 4 × 4 problems, a number of algorithms find lower the largest problems, we used q0 = 1.25 and qdec = 0.05. mean probabilistic makespans than B&B-N despite the fact Preliminary experiments with the 20 × 20 problems indicated that B&B-N terminates before the limit on CPU time and that q0 = 1.25 resulted in long runs with no solutions due to therefore finds approximately optimal solutions. This is an a large search space with few if any solutions. To avoid such artifact resulting from algorithms that simulate the same so- runs, we used q0 = 0.9, for which solutions could be found. lution multiple times. In B&B-N, a particular solution is The probabilistic makespans are based on confidence level only simulated once. In other algorithms, the same solution p = 0.95. Our primary evaluation criterion is the mean may be simulated multiple times leading to a bias to lower normalized probabilistic makespan (MNPM ) that each algo- probabilistic makespan values. Based on the theoretic model l D(a,l) rithm achieves: MNPM (a, L) = |L| L Dlb (l) . L is a 1 of Beck & Wilson, these values still correspond to approxi- mately optimal solutions. set of problem instances, D(a, l) is the mean probabilistic Problem Unc. B&B Tabu 4.3 Analysis Size Level TBS I-BS TBS I-BS Overall the empirical results agree with those presented by 0.1 0.001 0 0 0 Beck & Wilson. Here, we will focus on investigations of 0.5 0 0.001 0.001 0.001 4×4 B&B-DQ-L and of the behavior of the heuristic algorithms. 1 0.02 -0.001 0.021 0.017 0.1 0.002 0 0.001 0.001 Branch-and-Bound Descending-Q Leaves 0.5 -0.002 0 0.005 0.004 6×6 B&B-DQ-L out-performs B&B-N across all problem sets 1 0.027 0.001 0.041 0.009 even when it is not able to reach q = 0. As an indication of 0.1 0 0 -0.001 0.002 the number of iterations, the mean minimum values q for each 0.5 0.004 0.004 0.006 0.002 10 × 10 problem size are: 4 × 4 : 0.007, 6 × 6 : 0.56, 10 × 10 : 1.00, 1 0.015 0.016 0.017 0.009 20 × 20 : 0.9. 0.1 0.009 0.010 0.011 0.015 For B&B-DQ-L, the deterministic durations defined by the 0.5 0.010 0.005 0.012 0.028 20 × 20 q value serve to guide and prune the search for each iteration 1 0.025 0.030 0.029 0.032 and, therefore, as with the heuristic algorithms (see below), the search is heuristically guided to the extent that solutions Table 3: The difference between the mean normalized proba- with low deterministic makespans also have low probabilis- bilistic makespans for runs using q0 and using q2 . The higher tic makespans. However, the characteristics of the solutions the value, the more the q2 runs out-performed the q0 runs. found by the search are unclear. Ideally, we would like the search with high q to find solutions with very good probabilis- tic makespans both because we wish to find good solutions it outperforms Tabu-I-BS, it will also have found better de- quickly and because the probabilistic makespan values are terministic solutions and/or be able to systematically search used to prune subsequent search. Analysis indicates that the solutions up to a higher threshold. In contrast, for problem first solution found by B&B-DQ-L is consistently better than sets where Tabu-I-BS outperforms B&B-I-BS, it will be due the first solution found by B&B-N and for the larger problems to finding better deterministic solutions. (10 × 10 and 20 × 20) the relative increase in solution quality Table 4 presents data using q = q2 . The mean normalized over subsequent iterations is greater for B&B-DQ-L. deterministic makespan (MNDM ) is the calculated as follows: Dq (a,l) MNDM (a, L) = |L| L Dq,min (l,B &B -I -B S ) . The nota- 1 l Heuristic Algorithms tion is as above with the addition of Dq,min (l, B&B-I-BS), To investigate the performance of the heuristic algorithms, the lowest deterministic makespan found by the B&B-I-BS we look at the performance differences coming from using algorithm over all runs on problem l. MNDM, therefore, pro- the q values, and the extent to which the performance of the vides a relative measure of the mean deterministic makespans heuristic algorithms depends on two factors: their ability to from the two algorithms: the higher the value, the worse is the find good deterministic solutions and the underlying correla- average makespan found relative to B&B-I-BS. The second tion between deterministic and probabilistic makespans in the measure (Iters) is the mean number of iterations performed experimental problems. by each algorithm. The Effect of the q Values Using a non-zero q value almost Problem Unc. B&B-I-BS Tabu-I-BS always results in better performance. This appears to be par- Size Level MNDM Iters MNDM Iters ticularly true when either the uncertainty or the problem size 0.1 1.000 100 1.000 76 increases. Table 3 shows the difference between mean nor- 0.5 1.000 100 1.000 78 4×4 malized probabilistic makespan when using q0 and q2 . On a 1 1.000 100 1.007 83 few problem sets, negative values indicate that the runs with 0.1 1.000 10 1.000 24 q0 deliver a better mean solution. However, by far the ma- 0.5 1.000 10 1.001 31 6×6 jority of the values are greater than 0 and their magnitude 1 1.000 11 1.000 21 increases with both uncertainty and problem size, indicating 0.1 1.000 1 1.002 5 increasingly good relative performance on the q2 problems. 0.5 1.000 1 1.004 5 10 × 10 We show below that one explanation for this performance is 1 1.000 1 1.004 5 that problem instances with q > 0 have a greater correlation 0.1 1.045 0 1.002 0 between deterministic and probabilistic makespans. 0.5 1.041 0 0.998 0 20 × 20 1 1.037 0 1.002 0 Finding Good Deterministic Makespans We hypothesize Table 4: The mean normalized deterministic makespan that the performance of the heuristic techniques (and B&B- (MNDM) and number of iterations (Iters) for B&B-I-BS and DQ-L) is partially dependent upon the ability to find solu- Tabu-I-BS. tions with low deterministic makespans. We looked at two measures of the performance of B&B-I-BS and Tabu-I-BS: the quality of the best deterministic solutions found and the Table 4 is consistent with our hypotheses. For those prob- number of iterations. Because B&B-I-BS performs system- lems sets with large performance differences (i.e., 10 × 10 atic search of all deterministic solutions with makespan below and 20 × 20) in probabilistic makespan, the better performing a given threshold, we hypothesize that on problem sets where algorithm does find better deterministic makespans. The Correlation Between Deterministic and Probabilistic served in heuristic algorithms based on using the determin- Makespan The explanatory power of an algorithm's ability istic makespan to filter the solutions which are to be simu- to find good deterministic makespans is, by itself, insufficient lated. It was argued, using detailed analysis of the experi- unless there is a correlation between the good deterministic mental data and results from an ancillary experiment, that the and good probabilistic makespans. It is reasonable to expect performance of these algorithms is affected by their ability to that the level of uncertainty has an impact on any correlation: find good deterministic makespans and the correlation in the at low uncertainty, the variations in duration are small, so we problems between the quality of deterministic and probabilis- can expect the probabilistic makespan to be relatively close tic makespans. The correlation data on problems with higher to the deterministic makespan. When the uncertainty level is uncertainty suggest that such algorithms may scale well to high, the distribution of probabilistic makespans for a single such problems. Central to the success of the heuristic al- solution will be wider, resulting in a lower correlation. We gorithms was the use of a q value that governs the extent hypothesize that this impact of uncertainty level contributes to which uncertainty (i.e., the variance) was represented in to the observed performance degradation (see Table 2) of the the durations of activities in deterministic problems. It was heuristic techniques with higher uncertainty levels. shown that such an incorporation of uncertainty data leads to We generated 100 new 10 × 10 deterministic JSP problem a stronger correlation between deterministic and probabilis- instances with the same generator and parameters used above. tic makespans, and suggests a corresponding ability to find The standard deviation for the duration of each activity in the better probabilistic makespans. 100 instances were generated independently for each of five References uncertainty levels uj {0.1, 0.5, 1, 2, 3} resulting in a total of 500 problem instances. For each instance and each of the [Beck and Fox, 2000] J. C. Beck and M. S. Fox. Dy- four q values above, we randomly generated and simulated namic problem structure analysis as a basis for constraint- 100 deterministic solutions. Using R [R Development Core directed scheduling heuristics. Artificial Intelligence, Team, 2004], we measured the correlation coefficient, r, for 117(1):31­81, 2000. each problem set. [Beck and Wilson, 2004] J.C. Beck and N. Wilson. Job shop scheduling with probabilistic durations. In Proceedings Unc. Level q0 q1 q2 q3 of the Sixteenth European Conference on Artificial Intelli- 0.1 0.9990 0.9996 0.9996 0.9995 gence (ECAI04), pages 652­656, 2004. 0.5 0.9767 0.9912 0.9917 0.9909 [Garey and Johnson, 1979] M. R. Garey and D. S. Johnson. 1 0.9176 0.9740 0.9751 0.9736 2 0.8240 0.9451 0.9507 0.9517 Computers and Intractability: A Guide to the Theory of 3 0.7381 0.9362 0.9418 0.9423 NP-Completeness. W.H. Freeman and Company, New York, 1979. Table 5: The correlation coefficient comparing deterministic [Laborie, 2003] P. Laborie. Algorithms for propagating re- and probabilistic makespans for a set of 10 × 10 probabilis- source constraints in AI planning and scheduling: Exist- tic JSPs. Each cell represents the correlation coefficient for ing approaches and new results. Artificial Intelligence, 10000 deterministic, probabilistic pairs. 143:151­188, January 2003. [Le Pape et al., 1994] C. Le Pape, P. Couronne, ´ Table 5 supports our hypothesis. As the uncertainty level D. Vergamini, and V. Gosselin. Time-versus-capacity increases, the correlation between the deterministic makespan compromises in project scheduling. In Proceedings of the and corresponding probabilistic makespan lessens. The Thirteenth Workshop of the UK Planning Special Interest strength of the correlation is somewhat surprising: even for Group, 1994. the highest uncertainty level, r is more than 0.94 for q2 and q3 . This suggests that the heuristic algorithms can be suc- [Nowicki and Smutnicki, 1996] E. Nowicki and C. Smut- cessfully applied to problem with higher uncertainty levels nicki. A fast taboo search algorithm for the job shop prob- provided the appropriate q value can be found. lem. Management Science, 42(6):797­813, 1996. The correlation results in Table 5 also provide an explana- [Nuijten, 1994] W. P. M. Nuijten. Time and resource con- tion for the effect of the q values: they increase the correlation strained scheduling: a constraint satisfaction approach. between deterministic and probabilistic makespans. PhD thesis, Department of Mathematics and Computing Science, Eindhoven University of Technology, 1994. 5 Conclusion [R Development Core Team, 2004] R Development Core In this paper, we presented and conducted empirical analy- Team. R: A language and environment for statistical sis of a number of algorithms to proactively solve the job computing. R Foundation for Statistical Computing, shop scheduling problem with probabilistic durations. Our Vienna, Austria, 2004. ISBN 3-900051-07-0. empirical studies have demonstrated that a novel algorithm, [Watson et al., 2002] J.-P. Watson, L. Barbulescu, L.D. B&B-DQ-L, based on iteratively reducing a parameter that Whitley, and A.E. Howe. Contrasting structured and ran- determines the validity of the lower bound results in equal dom permutation flow-shop scheduling problems: search- performance on small problems and much better performance space topology and algorithm performance. INFORMS on larger problems when compared to the previous branch- Journal on Computing, 14(1), 2002. and-bound technique. However, highest performance was ob-