Scheduling multi-stage parallel-processor services to minimize average response time

Journal of the Operational Research Society (2006) 57, 101–110

r 2006 Operational Research Society Ltd. All rights reserved. 0160-5682/06 $30.00 www.palgrave-journals.com/jors

Scheduling multi-stage parallel-processor services to minimize average response time A Allahverdi* and FS Al-Anzi Kuwait University, Safat, Kuwait The problem of scheduling on a multi-stage parallel-processor architecture in computer centres is addressed with the objective of minimizing average completion time of a set of requests. The problem is modelled as a flexible flowshop problem for which few heuristics exist in the flowshop scheduling literature. A new three-phase heuristic is proposed in this paper. An extensive computational experiment has been conducted to compare the performance of the existing heuristics and the proposed heuristic. The results indicate that the proposed heuristic significantly outperforms the existing ones. More specifically, the overall average error of the best existing heuristic is about five times that of the proposed heuristic while the overall average CPU time of the proposed heuristic is about half of the best existing one. More importantly, as the number of requests increases, the CPU time of the proposed heuristic decreases considerably (compared to the best existing heuristic) while the ratio of the error (of the best existing to the proposed heuristic) of about five times remains almost the same. Journal of the Operational Research Society (2006) 57, 101–110. doi:10.1057/palgrave.jors.2601987 Published online 27 April 2005 Keywords: scheduling; production; multi-stage; parallel-server; flexible flowshop

Introduction An internet service requires the processing of a request (job) coming from different clients (customers) on a multi-stage architecture where each stage usually consists of a pool of parallel processors (servers) performing the same operation. The number of parallel servers in a stage is determined by how critical this particular stage is to the overall quality of the service. This architecture is widely used in the internet since it provides flexibility in scalability and robustness. When a service request arrives to such an architecture it follows a predetermined order of different stages of the service. Usually, the amount of processing time of a request can be known beforehand. At any point of time, there is usually a set of service requests waiting to be processed. The order of providing the service to the available set of requests, significantly affects the average response time of the service. Therefore, it is essential to determine the best order for processing this set of requests in order to minimize the average response time. This performance measure ensures fairness to different clients and is one of the factors that characterize the quality of an internet service. The clients (customers) become dissatisfied as the average time gets large. The problem is an on-line one, in which requests are arriving in a period of time. However, we can use a static *Correspondence: A Allahverdi, Department of Industrial and Management Systems Engineering, Kuwait University, PO Box 5969, Safat, Kuwait. E-mail: [email protected]

version of the problem where there is a fixed number of requests. This model is valid since the requests are collected until the system becomes available after the previous batch of requests. Once it becomes available, the batch of accumulated requests are considered for processing next. Hence, this can be considered as a static system within a window of time that is equivalent in duration to the time taken to process the previously collected batch of requests. The width of the window depends on the system and the person scheduling it. This problem has been addressed in the literature in the context of machine scheduling known as the flexible multistage flowshop problem with the objective of minimizing the average (or total) completion time. Given the NP-hardness of the problem,1 implicit enumeration techniques and heuristics have been proposed to solve the problem in the literature. For a small number of jobs (requests), implicit enumeration techniques such as branch-and-bound have been proposed by Linn and Zhang,2 and Rajendran and Chaudhuri.3 Efficient heuristics, however, are necessary for a larger number of jobs. The literature survey reveals that different heuristics have been presented by Sridhar and Rajendran,4 Brah and Loo,5 Azizoglu et al,6 and Al-Anzi and Allahverdi.7 The problem has also been addressed in the context of machine scheduling for other performance measures such as makespan which denotes the completion time of the last request. This performance measure is useful in the context of multi-server internet services for situations where the set of requests are parts of a single transaction and

102 Journal of the Operational Research Society Vol. 57, No. 1

where the transaction cannot be considered complete unless all the requests are successfully executed. Recent work with the makespan performance measure includes Cheng et al,8 Choi and Lee,9 Moursli and Pochet,10 Grabowski and Pempera,11 Gendreau et al,12 and Negenman.13 A new heuristic is proposed in this paper for the objective of minimizing the average completion time. The proposed heuristic consists of three phases. Simulated Annealing (SA) is used in the first phase of the heuristic followed by a Diffusion and Infusion greedy algorithms phase. The last phase is a local linear rippling procedure. An extensive computational experiment has been conducted to compare the performance of the proposed heuristic and the existing heuristics of Sridhar and Rajendran,4 Brah and Loo,5 Azizoglu et al,6 and Al-Anzi and Allahverdi.7 The results indicate that the proposed new heuristic, significantly outperforms the existing ones in terms of the average error, the number of best solutions, and the standard deviation of the error. Specifically, the overall average error of the proposed heuristic, which is SA based, is about 0.2 times that of the best existing heuristic of Al-Anzi and Allahverdi7 (a genetic-based algorithm) while the overall average CPU

time of the proposed heuristic is about half of the best existing one. More importantly, as the number of requests increases, the CPU time of the proposed heuristic decreases considerably (compared to the best existing heuristic) while the ratio of the error (the proposed/the best) of about 0.2 times remains almost the same. In this paper, it is also shown that the overall average error of the first phase of our proposed algorithm (SA) is 0.956, while the overall average error of the first phase of the algorithm of Al-Anzi and Allahverdi7 (genetic algorithm (GA)) is 39.68 for the considered problems.

Problem definition Consider the configuration where there are m stages. Stage j (j ¼ 1, 2, y, m) consists of pj identical parallel servers, see Figure 1. There is a set of n requests available for scheduling. Every request i is to be processed by one of the servers in stage 1, then one of the servers in stage 2, and so on until it is processed by one of the servers in stage m. If all the servers at a stage are busy, then a request has to wait until one of the servers at that stage becomes available. A server at a given

Client

Client Client

Client

Client Internet

Client

Info

Requests

Multi-Stage Multi-Sever Service

000000

0000000

Stage 1

Figure 1

Stage 2

Stage m

A typical multi-stage parallel-processor Internet service architecture.

A Allahverdi and FS Al-Anzi—Multi-stage parallel-processor services 103

stage can only process one request at a time and no preemption is allowed. Let n m pj tk(j) Ai(j) Ci(j)

the number of requests the number of stages the number of parallel servers at the jth stage the processing time of the request at the kth position on the jth stage the earliest time that the ith server at the jth stage is available the completion time of the request at position i at the jth stage

At the beginning, all the servers are available since no request is being processed. Therefore, AiðjÞ ¼ 0 for all i and j We assume that a request at position i is processed by the earliest available server at the jth stage, for example, the rth server at the jth stage. Then, the completion time of a request at position i can be expressed as 9 8 p j > > > > min fA g þ t if j ¼ 1 > > kðjÞ iðjÞ = < k¼1 ( ) CiðjÞ ¼ pj > > > > > ; : max Ciðj1Þ ; minfAkðjÞ g þ tiðjÞ otherwise > k¼1

The availability is updated each time Cij is computed according to the following Arj ¼ Cij for j ¼ 1; 2; . . . ; m for the rth server that processed the request at position i. The total and average completion times (TCT, ACT) of all requests can be expressed as TCT ¼

n X

Ci;m

i¼1

ACT ¼

n 1X Ci;m n i¼1

The objective is to find a schedule of requests that minimizes ACT. Note that the TCT objective function is equivalent to ACT objective function since 1/n is a constant for a given set of n requests.

Existing heuristics The flexible multi-stage flowshop problem is the generalization of the multi-stage flowshop problem where there is only one server at each stage. It is known that even the twostage flowshop problem with the average completion time performance measure is NP-hard, see Gonzalez and Sahni.1 Therefore, the problem addressed in this paper is also

NP-hard demonstrating the need for efficient heuristics. The literature review reveals that Sridhar and Rajendran,4 Brah and Loo,5 Azizoglu et al,6 and Al-Anzi and Allahverdi7 are the only ones establishing heuristics for our problem. In the following, the existing heuristics are described.

ACK heuristic Azizoglu et al6 presented a branch-and-bound algorithm to find an optimal solution. They proposed three heuristics to find an upper bound for their branch-and-bound algorithm. The three heuristics are as follows: Heuristic 1. Stages are considered separately. At each stage, the problem is solved by using the Shortest Processing Time rule. The sequences found are imposed over all stages and the sequence that gives the minimum average completion time is selected. Heuristic 2. The same as Heuristic 1 except that the sequence is only used at the first stage. For the other stages, among the available requests assign the request with the shortest processing time to the earliest available server. Heuristic 3. The requests are ordered in a sequence according to the sequence proposed by Rajendran and Chaudhuri14 of a non-decreasing order of Pm j¼1 ðm  j þ 1Þti;j where i denotes a request. Requests are assigned to the earliest available server at each stage. In this paper, all the three heuristics are evaluated and the best of the three is chosen. This is denoted as the ACK heuristic throughout this paper.

The HO heuristic Brah and Loo5 have applied the existing heuristics designed for the regular flowshop problems to flexible flowshop problems with different performance measures including average completion time. They found that the heuristic by Ho15 performed the best among the others with respect to the average completion time minimization. The HO heuristic is as follows: 1. Let k ¼ 1 2. Obtain an initial sequence by arranging the requests in P ascending order of m j¼1 ðm  j þ 1Þti;j for every request i 3. Sort the initial solution using the bubble sort and call it the current solution 4. Set Z1 ¼ ACT 5. a. Sort the current solution by the insertion sort b. Sort the current solution by the non-adjacent pair-wise interchange method 6. Sort the current solution by the bubble sort 7. Set Z2 ¼ ACT 8. If kon4, and Z1aZ2 then k ¼ k þ 1, and go to Step 4, otherwise the current solution is the final solution. The insertion and bubble sort methods are well-known sorting algorithms in computer science, see Knuth.16

104 Journal of the Operational Research Society Vol. 57, No. 1

The SR heuristic 4

Sridhar and Rajendran were the first to propose a heuristic for the problem. They proposed a three-phase heuristic. An initial seed sequence is obtained in the first phase by using the Rajendran and Chaudhuri14 algorithm. This seed sequence is used as a starting sequence for the SA algorithm. Their heuristic is referred to as SR Heuristic in this paper.

8. Set T ¼ T*r where r is temperature updating factor, and go to Step 3 9. Select the best solution p1 and set it as the current sequence T is the current temprature, r is the updating (cooling) factor, and TF is the final temperature. It is known that repetition of Steps 5–8 improves the performance of the SA algorithm.

The AA heuristic

Phase II: Diffusion and Infusion algorithms

The heuristic of Al-Anzi and Allahverdi7 consists of three phases. In phase one, an initial sequence is obtained by applying a genetic-based algorithm. In phase two, the sequence obtained from phase one is improved by a repeated application of greedy algorithms. Finally, in phase three, the sequence acquired from phase two is further improved by a local search procedure. Their heuristic is referred to as the AA heuristic in this paper. The second and third phases of our proposed algorithm are the same as those of AA, which are described in the next section. In other words, the difference between AA and the one proposed in this paper is in phase one, in which a GA is used in AA while a simulated annealing algorithm is used in the current paper. It should be noted that of the three phases, the most important one is the first phase. It is indicated in the subsequent section that by using SA in this paper, phase one of the algorithm can be improved by more than 4000% over GA of AA in terms of the error.

Here we describe the two greedy algorithms of phase II separately.

Diffusion algorithm 1. Given an input sequence of n requests. 2. Set k ¼ 1 and current solution to be empty 3. Generate k candidate sequences by diffusing (splitting) the current solution into two parts at all possible k positions and inserting the kth request in the diffused sequence. 4. Compute partial ACT for all k candidate sequences. Among these candidates, select the one with the least ACT. 5. Update the one with the least ACT as a current solution. 6. Update k ¼ k þ 1 7. If k ¼ n þ 1 then stop, else go to Step 3. The Diffusion Algorithm described above was first used by Nawaz et al.17 for a different problem (regular flowshop) and a different performance measure (makespan).

The proposed heuristic (PH) Our proposed heuristic (PH) is described in this section. It consists of three phases. In phase one, an initial sequence is obtained by applying a SA algorithm. In phase two, the sequence obtained from phase one is improved by a repeated application of diffusion and infusion greedy algorithms. Finally, in phase three, the sequence acquired from phase two is further improved by a local linear rippling procedure. The description of each phase of the PH heuristic is explained next.

Phase I: Simulated Annealing Algorithm 1. 2. 3. 4. 5.

Get a random initial sequence p1 Set an initial temperature T If ToTF go to Step 9 Repeat Steps 5 to 8 k times Perform a random pairwise exchange to p1, and call the resulting sequence as p2 6. Let D ¼ ACT(p2)ACT(p1) 7. If Dp0, then set p1 ¼ p2, otherwise 7.1. p ¼ eD/T 7.2. Set p1 ¼ p2 with the probability p

Infusion algorithm Our Infusion algorithm makes log2(n) passes on the list of requests. Here, we assume that n is a power of 2. If not, we increase n to the closest multiple of 2 and fill the rest of the request slots by zero processing time requests which will be removed from the final request sequence. In pass number i, the list is evenly divided into subsequences, each of size 2i1. For every two subsequences j and j þ 1 that are to be infused, we iterate the infusion of every element in the subsequence j þ 1 into the subsequence j maintaining the best sequence that has the least average completion time in the produced subsequences. 1. 2. 3. 4.

Given an input sequence of n requests. Set the input sequence as current sequence For i ¼ 1, y, log2(n) Repeat Steps 4–10 Divide the current sequence into subsequences of size 2i1 5. For every two adjacent subsequences j and j þ 1 that will be infused repeat Steps 6–9 6. For every request k in subsequence j þ 1 from left to right, perform Steps 7–9, where 1pjon/2i1

A Allahverdi and FS Al-Anzi—Multi-stage parallel-processor services 105

1. 2. 3. 4. 5. 6. 7. 8.

Set i ¼ 1 Compute ACT of the current sequence, and call it ACT1 Exchange the requests in position i and i þ 1 Compute ACT of the current sequence, and call it ACT2 If ACT2oACT1, then go to Step 7 Exchange the requests in position i and i þ 1 Set i ¼ i þ 1 If ion, then go to Step 2

Policy and parameter settings Note that the policy of assigning a sequence of the requests at each stage can be one of two policies. The first policy is to enforce the initial sequence (the sequence fed to stage one) to all the subsequent stages. The second policy is that a request departing from a previous stage is assigned to the earliest available server from the current stage. If there is more than one request available when a server is free, the priority is given to the one with the shortest processing time. In our proposed heuristic we adopt the second policy. Setting the parameters for Phase I of our proposed heuristic is essential in achieving a good performance. After extensive experimentation, the parameters are set as follows; T ¼ 0.1, r ¼ 0.98, TF ¼ 0.0001, and k ¼ 50. In Phase II, the greedy algorithms are applied in the sequence of Infusion–Diffusion–Infusion repeatedly. This process is repeated five times since no significant improvement was observed beyond this. It should be noted that there is no guarantee that each time a better solution will be obtained. Therefore, among the five repetitions the best one is always kept as the current best solution. Experimentation has shown that the proper sequence of greedy algorithms is Infusion–Diffusion–Infusion since other permutations did not perform as well. Experimentation has also shown that using Diffusion or Infusion alone did not perform well. Similarly, Phase III is repeated and it has been observed that five repetitions of the local linear rippling procedure was sufficient to produce a good solution. It can be shown that the time complexity of phases I, II, and III are O(nm), O(n2m log n), and O(n2m), respectively. Therefore, the time complexity of PH is O(n2m log n).

The three existing heuristics of ACK, SR, and AA along with our proposed heuristic PH were implemented in C on a Sun Sparc 20, and evaluated with respect to average error, standard deviation of the error, and the number of times yielding the best solution. We also evaluated the first phase of heuristics AA and PH since the main difference between the two is in the fist phase. The first phase of AA is denoted by GA while that of PH is denoted by SA. The results for HO are not reported due to its large CPU time requirement with an inferior performance compared to the existing heuristic of AA. Al-Anzi and Allahverdi7 reported that the CPU time of HO increases significantly as the number of requests increases while the CPU times of the other heuristics increase moderately. Moreover, Al-Anzi and Allahverdi7 also reported that the error performance of their heuristic AA was better than that of HO while the CPU time of AA was much less than HO. Therefore, we will not include HO in our comparison. The processing times were randomly generated from a uniform distribution (1, 100). In the scheduling literature, most researchers have used this distribution in their experimentation, for example, Wang et al,18 Pan and Chen,19 Al-Anzi and Allahverdi,20 and Allahverdi and AlAnzi.21 The reason for using a uniform distribution is that the variance of this distribution is large and if a heuristic

Error (%)

Phase III: Local linear rippling procedure

Comparison of heuristics

45 40 35 30 25 20 15 10 5 0

GA SA

20

30

Figure 2

40

50 60 70 80 Number of requests

90

100

Error comparison of SA and GA.

14 12 10 Std

7. Generate candidate sequences by infusing the kth request into each possible slot of j subsequence 8. Compute the partial ACT for each candidate sequence. Among these candidates, select the one with the least ACT 9. Update the one with the least ACT as the jth sequence 10. Join all subsequences resulting from Steps 5–9 into one sequence and let it be the current sequence

8 6 GA SA

4 2 0 20

30

Figure 3

40

50 60 70 80 Number of requests

90

Std comparison of SA and GA.

100

106 Journal of the Operational Research Society Vol. 57, No. 1

Table 1

Experimental results

ACK

SR

SA

n

m

PB

Error (%)

Std

PB

Error (%)

Std

PB

Error (%)

Std

20 20 20 20 20

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

31.374 21.094 24.451 27.264 26.082

16.420 11.740 13.480 13.500 13.040

100.000 36.667 33.333 23.333 33.333

0.000 0.284 0.649 1.248 1.674

0.000 0.400 0.980 1.550 2.720

76.667 40.000 36.667 43.333 43.333

0.009 0.184 0.381 0.324 0.300

0.010 0.300 0.610 0.540 0.530

30 30 30 30 30

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

34.803 31.813 30.481 33.691 26.951

13.660 13.900 12.060 11.370 10.980

53.333 43.333 13.333 16.667 13.333

0.033 0.266 0.710 0.877 1.074

0.040 0.450 0.710 1.210 1.390

36.667 3.333 20.000 23.333 20.000

0.049 0.318 0.241 0.378 0.250

0.050 0.360 0.410 0.530 0.360

40 40 40 40 40

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

36.786 32.671 34.088 32.998 29.658

11.850 12.360 9.820 12.890 9.260

16.667 6.667 10.000 3.333 6.667

0.133 0.321 0.773 1.037 1.706

0.090 0.220 1.130 1.220 1.700

0.000 3.333 0.000 10.000 6.667

0.192 0.350 0.395 0.534 0.462

0.080 0.290 0.360 0.670 0.560

50 50 50 50 50

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

41.202 38.422 37.603 33.158 32.799

10.180 10.250 10.280 9.800 8.710

26.667 6.667 6.667 0.000 16.667

0.201 0.446 0.565 1.425 0.985

0.160 0.340 0.430 1.670 1.580

0.000 3.333 3.333 10.000 0.000

0.415 0.590 0.427 0.474 0.667

0.120 0.370 0.310 0.410 0.670

60 60 60 60 60

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

41.816 36.647 33.646 36.309 32.820

10.990 11.040 8.910 9.510 9.290

26.667 0.000 3.333 0.000 6.667

0.353 0.831 0.838 1.255 1.440

0.230 0.390 0.870 0.750 1.220

0.000 0.000 0.000 3.333 0.000

0.693 0.805 0.785 0.761 0.783

0.140 0.360 0.350 0.420 0.390

70 70 70 70 70

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

43.401 39.167 36.234 33.454 34.309

8.270 7.760 9.150 8.970 11.450

30.000 3.333 0.000 6.667 0.000

0.466 0.808 1.348 1.230 2.183

0.320 0.520 0.980 0.990 1.890

0.000 0.000 0.000 0.000 0.000

0.996 1.088 1.194 1.033 1.208

0.210 0.380 0.510 0.430 0.550

80 80 80 80 80

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

42.574 38.379 39.557 36.466 34.524

9.200 8.920 10.490 10.060 9.570

20.000 0.000 0.000 0.000 0.000

0.722 1.198 1.351 1.505 1.803

0.400 0.540 0.910 0.860 1.080

0.000 0.000 0.000 0.000 0.000

1.229 1.492 1.537 1.384 1.423

0.210 0.340 0.470 0.640 0.520

90 90 90 90 90

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

45.616 35.561 36.088 33.610 34.822

6.880 7.650 8.290 8.420 10.450

30.000 0.000 0.000 0.000 0.000

0.803 1.538 1.742 2.116 2.086

0.600 0.450 0.780 1.030 1.020

0.000 0.000 0.000 0.000 0.000

1.628 1.912 1.818 1.726 1.548

0.260 0.470 0.370 0.700 0.610

100 100 100 100 100

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

45.506 39.770 35.091 34.679 32.805

6.570 9.620 8.030 9.050 8.870

13.333 0.000 0.000 0.000 0.000

1.302 1.727 2.096 1.912 2.244

0.580 0.650 0.660 0.790 0.810

0.000 0.000 0.000 0.000 0.000

2.034 2.360 2.370 1.934 2.360

0.340 0.550 0.670 0.660 0.630

0.000

34.894

10.288

13.481

1.096

0.829

8.518

0.956

0.416

Mean

A Allahverdi and FS Al-Anzi—Multi-stage parallel-processor services 107

Table 1 Continued

GA

AA

PH

n

m

PB

Error (%)

Std

PB

Error (%)

Std

PB

Error (%)

Std

20 20 20 20 20

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

39.589 34.067 30.030 36.772 36.264

13.210 16.110 9.370 13.340 12.810

96.667 16.667 20.000 3.333 13.333

0.015 0.716 1.301 1.773 1.447

0.080 0.770 1.660 1.680 1.920

100.000 63.333 43.333 60.000 60.000

0.000 0.160 0.311 0.154 0.213

0.000 0.300 0.550 0.280 0.440

30 30 30 30 30

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

42.193 38.199 39.470 37.073 31.327

13.550 12.370 10.270 8.910 8.960

83.333 10.000 3.333 16.667 10.000

0.019 0.679 1.236 0.640 1.611

0.050 0.710 1.360 0.900 1.770

93.333 26.667 36.667 36.667 33.333

0.002 0.138 0.142 0.240 0.196

0.000 0.210 0.310 0.440 0.330

40 40 40 40 40

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

42.711 38.048 41.114 37.583 35.167

11.090 7.950 10.000 9.770 7.610

100.000 16.667 10.000 16.667 20.000

0.000 0.482 0.871 1.021 0.771

0.000 0.530 1.160 0.960 0.870

93.333 36.667 26.667 33.333 23.333

0.001 0.147 0.217 0.322 0.291

0.000 0.200 0.300 0.550 0.440

50 50 50 50 50

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

46.291 43.008 42.400 38.806 36.092

9.020 9.080 9.380 8.440 8.190

90.000 36.667 26.667 33.333 36.667

0.002 0.320 0.432 0.521 0.479

0.000 0.510 0.660 0.900 0.770

86.667 50.000 53.333 60.000 36.667

0.005 0.107 0.080 0.065 0.253

0.010 0.180 0.150 0.120 0.570

60 60 60 60 60

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

45.235 39.516 38.731 41.114 37.073

10.960 9.180 8.760 8.250 11.540

93.333 46.667 33.333 33.333 36.667

0.000 0.244 0.258 0.454 0.407

0.000 0.420 0.350 0.720 0.620

80.000 46.667 60.000 53.333 50.000

0.005 0.104 0.074 0.085 0.159

0.010 0.180 0.190 0.150 0.270

70 70 70 70 70

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

47.638 43.214 37.723 38.342 36.960

7.510 9.060 7.180 7.310 7.700

100.000 30.000 30.000 30.000 33.333

0.000 0.173 0.492 0.592 0.380

0.000 0.220 0.710 0.980 0.490

93.333 66.667 73.333 63.333 66.667

0.001 0.064 0.065 0.112 0.069

0.000 0.160 0.180 0.230 0.120

80 80 80 80 80

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

47.564 40.608 40.592 39.673 39.315

9.260 8.840 8.920 8.740 8.180

90.000 43.333 23.333 20.000 30.000

0.001 0.175 0.240 0.504 0.340

0.000 0.430 0.330 0.620 0.490

93.333 56.667 76.667 76.667 66.667

0.000 0.049 0.037 0.020 0.073

0.000 0.110 0.120 0.040 0.150

90 90 90 90 90

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

45.780 38.970 41.046 37.794 38.775

6.750 6.910 7.740 7.520 9.740

86.667 36.667 43.333 60.000 16.667

0.001 0.120 0.366 0.289 0.547

0.000 0.170 0.650 0.510 0.640

76.667 63.333 56.667 36.667 83.333

0.001 0.065 0.038 0.226 0.070

0.000 0.130 0.060 0.370 0.200

100 100 100 100 100

2 3 4 5 6

0.000 0.000 0.000 0.000 0.000

48.868 43.080 36.305 38.290 37.398

5.950 7.990 7.420 8.060 8.610

83.333 40.000 26.667 43.333 30.000

0.001 0.217 0.410 0.369 0.427

0.000 0.400 0.540 0.580 0.670

83.333 60.000 73.333 56.667 70.000

0.001 0.049 0.032 0.087 0.038

0.000 0.130 0.090 0.170 0.080

0.000

39.685

9.278

40.000

0.474

0.618

60.815

0.102

0.189

Mean

108 Journal of the Operational Research Society Vol. 57, No. 1

100.00

Error (%)

10.00 1.00 0.10 0.01 20

30

40

50 60 70 80 Number of Requests ACK

AA

SR

PH

90

100

90

100

90

100

Error versus n.

Figure 4

80.00 70.00 60.00

PB

50.00 40.00 30.00 20.00 10.00 0.00 20

30

40

50 60 70 80 Number of Requests

Figure 5

ACK

AA

SR

PH

PB versus n.

100.00 10.00 Std

performs well with such a distribution, it will most probably perform well with other distributions. Problem data are generated for a different number of requests ranging from 20 to 100 in increment of 10. The number of stages considered is 2–6 while at each stage the number of parallel servers is randomly generated from a uniform discrete distribution from 2 to 5. We compare the performance of the heuristics for 30 replicates using three measures: average percentage error (Error), standard deviation (Std), and the number of times the best solution is obtained (PB). The percentage error is defined as 100* (Heuristic ErrorBest Heuristic Error)/Best Heuristic Error. The Best Heuristic Error is the error of the heuristic yielding minimal error. Both PH and AA algorithms consist of three phases where they differ only on the first phase where PH uses SA and AA uses GA. Figure 2 compares the performance of SA and GA in terms of the overall average percentage error. It is clear that SA is superior to GA. More specifically, the overall average error of GA is 39.68 while that of SA is 0.956, which is an improvement of 4050%. Figure 3 compares the performance of SA and GA in terms of standard deviation. The overall average standard deviation of GA is 9.278 while that of SA is 0.416. It is clear that SA outperforms GA by 2130% in terms of the standard deviation. This improvement of SA over GA will reflect on the overall performance of PH over AA as will be discussed next. Table 1 shows the results of running the existing and the proposed heuristics for all combinations of the number of requests and the number of stages. Each entry in the table represents the average of the 30 replicates where for every replicate a configuration of the processing time and the number of servers per stage are generated randomly. Each heuristic is evaluated for the same configuration to ensure accurate assessment of the different heuristics. Figures 4–6 illustrate the performance of the heuristics with respect to the number of requests. Due to the poor performance of ACK, Figures 4 and 6 have a semilogarithmic scale for a more vivid comparison. It is clear that among the existing heuristics in the literature AA and SR significantly outperform ACK. The figures also show that AA, in general, performs much better than SR in terms of all the three performance measures especially for large number of requests. Hence, AA is the best among the existing heuristics. As can be seen from Figures 4–6, PH performs better than AA in terms of the average error. The same can be said for the other performance measures (standard deviation and the number of best solutions) for the PH and AA heuristics. More specifically, the overall average of errors of ACK, SR, AA, and the proposed heuristic PH are 34.894, 1.096, 0.474, and 0.102, respectively. The overall average percentage of best solutions (PB) of ACK, SR, AA, and the proposed heuristic PH are 0, 13.48, 40, and 60.81 while the overall average Std are 10.28, 0.83, 0.62 and 0.19, respectively.

1.00 0.10 0.01

20

30

40

50 60 70 80 Number of Requests

Figure 6

ACK

AA

SR

PH

Std versus n.

Clearly ACK is not recommended because of its extremely poor performance. PH outperforms SR since the overall average error of SR is 10.79 times that of PH while the CPU time of PH is about 3.11 times that of SR. PH also

A Allahverdi and FS Al-Anzi—Multi-stage parallel-processor services 109

100.000

1.000

Ratio

Error (%)

10.000

0.100 0.010 0.001 2

3

4 5 Number of Stages ACK

AA

SR

PH

6

PB

80 60 40 20 0 4 5 Number of Stages

Figure 8

ACK

AA

SR

PH

6

10.000 Std

30

40

50 60 70 80 Number of Requests

90

100

Comparison of AA and PH (PH/AA).

1.000 0.100 0.010 0.001 3

Figure 9

that the ratio of the error (PH/AA) remains almost the same (about 0.2) while the ratio of CPU time decreases exponentially as the number of requests increases. Therefore, PH is superior to all the existing heuristics. Figures 7–9 illustrate the performance of the heuristics with respect to the number of stages. Again, the semilogarithmic scales are used in Figures 7 and 9 due to the poor performance of ACK. In general, for all number of stages, the proposed PH heuristic outperforms all the existing heuristics in terms of all the three performance measures. It can be seen that the performance measures slightly deteriorate as the number of stages increases for all the heuristics.

Concluding remarks

PB versus m.

100.000

2

20

Figure 10

100

3

Ratio of Error Ratio of CPU

Error versus m.

Figure 7

2

5 4.5 4 3.5 3 2.5 2 1.5 1 0.5 0

4 5 Number of Stages ACK

AA

SR

PH

6

Std versus m.

outperforms AA since the overall average error of AA is 4.67 times that of PH while the CPU time of PH is about 0.48 times that of AA. Figure 10 shows the comparison of PH and AA in terms of CPU time and error. The figure shows

The problem of scheduling on a multi-stage parallel-server architecture in computer centres is addressed in this paper with respect to the average completion time of a set of requests. This problem can be modelled as a flexible flowshop problem. The flexible flowshop literature review reveals that there exist few heuristics to minimize average completion time. In this paper, we propose a new heuristic for this problem that consists of three phases; SA algorithm, Diffusion and Infusion greedy algorithms, and a local linear rippling procedure. An extensive computational experiment has been conducted to compare the existing and proposed heuristics. The results indicate that the proposed heuristic significantly outperforms the best existing heuristic where the overall average error of the proposed heuristic is much smaller than that of the best heuristic while the CPU time of the proposed heuristic is less than that of the best exiting heuristic. It is shown that by using SA proposed in this paper, phase one of the algorithm can be improved by more than 4000% over GA of best existing algorithm in the literature in terms of the error. SA is a well-known optimization technique and hence it has many applications. This paper shows that the performance of the SA technique can be enhanced significantly by

110 Journal of the Operational Research Society Vol. 57, No. 1

applying greedy and local optimization techniques to its results. Moreover, since SA is a global optimization technique, the use of a computed seed does not produce a better result than using a seed that is randomly chosen. The approach used in this paper can be extended to problems with other objective functions such as makespan and maximum lateness.

Acknowledgements—This research was supported by Kuwait University Research Administration project number EO 05/02.

References 1 Gonzalez T and Sahni S (1978). Flow shop and job shop schedules. Opns Res 26: 36–52. 2 Linn R and Zhang W (1999). Hybrid flowshop scheduling: a survey. Comput Ind Eng 37: 57–61. 3 Rajendran C and Chaudhuri D (1992). A multi-stage parallelprocessor flowshop problem with minimum flowtime. Eur J Opl Res 57: 111–122. 4 Sridhar J and Rajendran C (1993). Scheduling in a cellular manufacturing system: a simulated annealing approach. Int J Prod Res 31: 2927–2945. 5 Brah SA and Loo LL (1999). Heuristics for scheduling in a flow shop with multiple processors. Eur J Opl Res 113: 113–122. 6 Azizoglu M, Cakmak E and Kondakci S (2001). A flexible flowshop problem with total flow time minimization. Eur J Opl Res 132: 528–538. 7 Al-Anzi F and Allahverdi A (2002). Flexible multi-stage parallel-server scheduling for internet service architecture. Int J Parallel Distrib Systems Networks 5: 134–142. 8 Cheng TCE, Lin BMT and Toker A (2000). Makespan minimization in the two-machine flowshop batch scheduling problem. Navel Res Log 47: 128–144.

9 Choi AH and Lee JSL (2000). A sequence algorithm for minimizing makespan in multi-part and multi-machine flowshop case. Integrated Manuf Systems 11: 62–73. 10 Moursli O and Pochet Y (2000). A branch-and-bound algorithm for the hybrid flowshop. Int J Prod Econ 64: 113–125. 11 Grabowski J and Pempera J (2000). Sequencing of jobs in some production system. Eur J Opl Res 125: 535–550. 12 Gendreau M, Laporte G and Guimaraes EM (2001). A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times. Eur J Opl Res 133: 183–189. 13 Negenman EG (2001). Local search algorithms for the multiprocessor flow shop scheduling problem. Eur J Opl Res 128: 147–158. 14 Rajendran C and Chaudhuri D (1991). An efficient heuristic approach to the scheduling of jobs in a flowshop. Eur J Opl Res 61: 318–325. 15 Ho JC (1995). Flowshop sequencing with mean flowtime objective. Eur J Opl Res 81: 571–578. 16 Knuth DE (1973). The Art of Computer Programming: Sorting and Searching. Addison-Wesley: MA, USA. 17 Nawaz M, Enscore E and Ham I (1983). A heuristic for the m-machine, n-job flowshop sequencing problem. OMEGA Int J Mngt Sci 11: 91–95. 18 Wang MY, Sethi SP and Van De Velde SL (1997). Minimizing makespan in a class of reentrant shops. Opns Res 45: 702–712. 19 Pan CH and Chen JS (1997). Scheduling alternative operations in two-machine flow-shops. J Opl Res Soc 48: 533–540. 20 Al-Anzi F and Allahverdi A (2001). The relation between threetired client-server internet database and two-machine flowshop. Int J Parallel Distrib Systems Networks 4: 94–101. 21 Allahverdi A and Al-Anzi F (2002). Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications. Comput Opns Res 29: 971–994.

Received April 2004; accepted February 2005 after one revision