The efficiency of a new greedy heuristic for solving permutation flowshop scheduling problem.

Ancau, Mircea

1. INTRODUCTION

The flowshop scheduling problem (FSP) plays an important role in the field of combinatorial optimization NP-hard problems. Despite its apparent simple definition, this problem is very difficult to solve optimally in a polynomial time. The main problem objective is to establish the manufacturing sequence of n jobs processed on m machines, so that the total completion time (Cmax) or makespan is minimum. A comprehensive list of the problem assumptions sorted by categories can be found in (Gupta & Stafford, 2006). The heuristic techniques for solving FSP are grouped in: constructive heuristics and improvement heuristics. The constructive heuristic methods build a feasible schedule, based on some specific rules, while the improvement heuristics improve a previously generated schedule by applying some specific procedures.

The classic algorithm of Johnson (Johnson, 1954) builds the optimal schedule for the case of n jobs on two machines. In the case of three or more machines, the problem becomes NP-complete, even if there are particular cases in which the Johnson algorithm may still be applied. There are heuristics which divide the m machines into two groups, called virtual machines and subsequently apply the algorithm of Johnson (Campbell et al, 1970; Koulamas, 1988). Other heuristics techniques make use of slope index (Palmer, 1965), or weight as in (Gupta, 1971; Hundal & Rajgopal, 1988) assigned to each job. Then the jobs are sorted using the weights as sort key, to create a feasible schedule. NEH algorithm (Nawaz et al, 1983) is recognized as the champion in this field of heuristic techniques (Taillard, 1990). Many heuristic techniques are based on NEH, but propose different starting sequences.

The algorithm presented in this research, builds the schedule by applying a greedy technique to select candidates job and place them into the list. This technique has the advantage of simplicity and ease to program on the computer. The results are very closed to those of NEH. A weak point of the proposed method is the higher CPU time for large size problems. Future research will try to improve this.

2. THE NEW GREEDY HEURISTIC

Let consider a set of n jobs ([J.sub.1], [J.sub.2], [J.sub.n]). The criterion upon the greedy selection is made is [C.sub.max]. The outline of the algorithm is the following:

a) From the set of n jobs, find the ordered pair of jobs with the minimum processing time. There will be necessary n(n-1) ordered pair of jobs to check.

b) Set k = 2.

c) From the remaining (n-k) jobs, select the best candidate and its relative position, to be appended in the partial ordered sequence. The job and its relative position is selected according to minimum makespan criterion for (k+1) jobs of the partial sequence.

d) If the set of remaining (n-k) jobs is empty, list the n-jobs ordered sequence, or schedule, and its total completion time, as final solution.

e) Or else, set k = k + 1, and go to step (c).

3. THE COMPUTATIONAL COMPLEXITY

The first phase of the algorithm requires the partial processing time calculation for n x (n -1) ordered pairs of jobs. If we call [t.sup.(2J).sub.m] the makespan of a partial sequence involving 2 jobs, then the necessary running time of this phase is:

n x (n - 1) x [t.sup.(2J).sub.m]; (1)

The selection of the first starting pair of jobs is similar to that of SPIRIT (Widmer & Hertz, 1989). Unlike the SPIRIT algorithm in which the insertion of jobs is made randomly, in the proposed algorithm, each new job and its relative position are selected from the set of remaining jobs, according to the criterion of minimum increasing of partial processing time. When the third job is inserted, we need to select, from the remaining (n-2) jobs, a single candidate and its relative position among three possibilities. This thing requires the examination of 3 x (n - 2) possible variants. For the fourth job insertion the examination of 4 x (n - 3) variants will be necessary and so on. The necessary time for the insertion of all (n-2) jobs is calculated by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; (2)

where [t.sup.(kJ).sub.m] is the makespan of partial sequences for k jobs. Equation (2) shows that the asymptotic time complexity of the selective greedy algorithm is [THETA]([n.sup.3]).

4. NUMERICAL RESULTS

The algorithm was tested on four groups of benchmark problems from OR Library (see http://mscmga.ms.ic.ac.uk /info.html) which are Taillard's test instances. Table 1 and Table 2 show the computational results of these test instances. The results corresponding to NEH heuristic were taken from (Agarwal et al,2006) only for the evaluation of performances. The Gap, in percents, which is being referred to as the difference between the Makespan and Upper Bound, was calculated by:

Gap = Makespan - UB/UB - 100%; (3)

Until now researches have demonstrated the efficiency of NEH heuristic, against most recognized heuristics (Ruiz and Morato, 2005), (Agarwal et al,2006), (Gupta et al, 2006), (Chakraborty and Laha,2007). This is another reason why, in this paper, the performances of the proposed algorithm are related to those of NEH algorithm.

The numerical experiments were performed on a PC with an Intel Pentium processor at 1.6 GHz. The proposed greedy algorithm was tested on more than eighty test instances. On nineteen cases, the greedy algorithm found better solution than NEH. In most of test instances examined, the solutions found by greedy algorithm are very close to those of NEH.

Looking at the average gaps in Table 2, from Taillard's instances of size 20x5, 20x10 and 20x20, one may conclude that for the SG algorithm, the average gap increases as the number of machines increase. But this conclusion does not stand while the average gap for the size 20x20 is lower than that of size 20x10.

Nevertheless, more important to remark is the constancy of the results' quality in the same size instance. The algorithm have large CPU times for larger instances and this fact is owed to its higher computational complexity degree.

5. CONCLUSION

This paper presents an original algorithm for solving the flowshop scheduling problem. This variant is a constructive heuristic based on a greedy selection. The algorithm is elegant, very simple to implement and offer high quality solutions.

The numerical results show the high performances of the algorithm, similar to those of NEH. In the same time, we must remark the constancy of solutions for the same size of instance. A possibility may yet occur that several starting pair of jobs will have the same minimum processing time. In the present research, the algorithm considered as starting pair of jobs, the first pair which met the selection criterion, but future research may take into consideration the other pairs of jobs which fulfill the mentioned condition.

For higher test instances with more than 150 jobs, the CPU time becomes too high. This situation appears due to the high calculation complexity degree of the greedy algorithm. Future research have to solve this problem in order to reduce CPU time.

It will be taken into consideration the possibility to introduce some random factors in order to escape from local optimum, and transform the algorithm from a deterministic one into a stochastic one.

6. ACKNOWLEDGEMENTS

The present research is a part of the research grant CNCSIS code 188 / 2009, supported by ANCS Bucharest, Romania.

7. REFERENCES

Agarwal, A., Colak, S., Eryarsoy, E. (2006) Improvement heuristic for the flow-shop scheduling problem: An adaptive-learning approach. European Journal of Operational Research, 169, p.801-815

Campbell, H.G., Dudek, R.A., Smith, M.L. (1970) A heuristic algorithm for the n job, m machine sequencing problem. Management Science, 16 (10), B630-B637

Chakraborty, U.K., Laha, D. (2007) An improved heuristic for permutation flowshop scheduling. Int. J. Information and Communication Technology, Vol.1. No.1, p.89-97

Gupta, J.N.D. (1971) A functional heuristic algorithms for the flowshop scheduling problem. Operational Research Quarterly, 22 (1), p.39-47

Gupta, J.N.D.; Stafford Jr., E.F. (2006) Flowshop scheduling research after five decades. European Journal of Operational Research, 169, p.699-711

Hundal, T.S., Rajopal, J. (1988) An extension of Palmer's heuristic for the flow shop scheduling problem. International Journal of Production Research, 26 (6), p.1119-1124

Johnson, S.N. (1954) Optimal two--and three--stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, p.61-68

Kuolamas, C. (1988) A new constructive heuristic for the flowshop scheduling problem. European Journal of Operational Research Society, 105, p.66-71

Nawaz, M., Enscore Jr., E.E., Ham, I. (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, The International Journal of Management Science, 11 (1), p.91-95

Palmer, D. (1965) Sequencing jobs through a multi-stage process in the minimum total time--a quick method of obtaining a near optimum. Operational Research Quarterly, 16 (1), p.101-107

Ruiz, R., Morato, C. (2005) A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165, p.479-494

Taillard, E. (1990) Some efficient heuristic methods for the flow-shop sequencing problem. European Journal of Operational Research, 47, p.67-74

Widmer, M., Hertz, A. (1989) A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research, 41, p.186-193

Tab. 1. Makespans and gaps for Taillard's benchmark
problems

Problem Upper Makespan Gap [%]
instance bound NEH Greedy NEH Greedy

ta001-20x5 1278 1286 1286 0.62 0.62
ta003-20x5 1081 1159 1141 7.21 5.55
ta004-20x5 1236 1305 1301 5.58 5.25
ta005-20x5 1195 1228 1224 2.76 2.42
ta006-20x5 1239 1278 1264 3.14 2.01
ta007-20x5 1230 1291 1277 4.95 3.82
ta008-20x5 1108 1151 1144 3.88 3.24
ta009-20x10 1582 1680 1600 6.19 1.13
ta010-20x20 2237 2320 2289 3.71 2.32
ta011-50x5 2751 2782 2782 1.12 1.12
ta012-50x5 2782 2790 2787 0.28 0.17
ta013-50x10 3006 3178 3157 5.72 5.02
ta014-50x10 3091 3257 3206 5.37 3.72
ta015-50x20 3771 4082 4052 8.24 7.45
ta016-50x20 3696 4079 3973 10.36 7.49
ta017-100x5 5268 5348 5304 1.51 0.68
ta018-100x5 5454 5489 5485 0.64 0.56
ta019-200x10 10494 10716 10625 2.11 1.24

Tab. 2. Average gap for Taillard benchmark problems

 Instance size Number of Average gap [%]
 instances NEH Greedy

20 x 5 10 3.246 3.365
20 x 10 10 4.587 5.643
20 x 20 10 3.721 5.46
50 x 5 10 0.723 2.047
50 x 10 10 4.567 5.485
50 x 20 10 8.329 8.606
100 x 5 10 0.476 0.945
200 x 10 10 1.282 1.550