Efficient Heuristic to Minimize Makespan in Single Machine Scheduling Problem with Unrelated Parallel Machines

P. Sivasankaran, T. Sornakumar, R. Panneerselvam

.

DOI: 10.4236/iim.2012.23022                

Abstract

This paper discusses an efficient heuristic to minimize the makespan of scheduling n independent jobs on m unrelated parallel machines. The problem of scheduling the jobs on the unrelated parallel machines is combinatorial in nature. Hence, the heuristic approach is inevitable for quicker solution. In this paper, a simple and efficient heuristic is designed to minimize the makespan of scheduling n independent jobs on m unrelated parallel machines. A mathematical model is also presented for this problem. A factorial experiment is used to compare the results of the proposed heuristic with that of a mathematical model by taking “Method” (Heuristic and Model) as the first factor and “Problem Size” (No. of machines X No. of Jobs: 2X5, 2X6, ……, 2X9, 3X5, 3X6, ……, 3X9, ……., 5X5, 5X6, …5X9) as the second factor. It is found that there is no significant difference between the results of the proposed heuristic and that of the mathematical model. Further, the mean percent error of the results obtained by the heuristic from the optimal results obtained by the model is 2.336 %. The heuristic gives optimal solution for 76.67 % of the problems.

Keywords

Makespan, Heuristic, Unrelated Parallel Machines, Mathematical Model, ANOVA

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. Panneerselvam, “Production and operations management (Second Edition),” PHI Learning Private Limited, New Delhi, 2005.
[2]	S. L. Van De Velde, “Duality-based algorithms for scheduling unrelated parallel machines,” ORSA Journal of Computing, Vol. 5, pp. 182–205, 1993.
[3]	C. A. Glass, C. N. Potts, and P. Shade, “Unrelated parallel machine scheduling using local search,” Mathematical and Computer Modelling, Vol. 20, pp. 41–52, 1994.
[4]	Francis Sourd “Scheduling tasks on unrelated machines: Large neighbourhood improvement procedures,” Journal of Heuristics, Vol. 7, pp. 519–531, 2001.
[5]	E. Mokotoff and P. Chretienne, “A cutting plane algorithm for the unrelated parallel machine scheduling problem,” European Journal of Operational Research, Vol. 141, pp. 515–525, 2002.
[6]	E. Mokotoff and J. L. Jimeno, “Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem,” Annals of Operations Research, Vol. 117, pp. 133–150, 2002.
[7]	A. M. A. Hariri and C. N. Potts, “Heuristics for scheduling unrelated parallel machines,” Computers and Operations Research, Vol. 18, pp. 323–331, 1991.
[8]	N. Piersman and W. Van Dijk, “A local search heuristic for unrelated parallel machine scheduling with efficient neighbourhood search,” Mathematical and Computer Modelling, Vol. 24, pp. 11–19, 1996.
[9]	M. Ghirardi and C. N. Potts, “Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach,” European Journal of Operational Research, Vol. 165, pp. 457–467, 2005.
[10]	B.Monien and A. Woclaw “Scheduling unrelated parallel machines computational results,” Experimental Algorithms, Springer, Berlin/Heidelberg, Vol. 4007, pp. 195– 206, 2006.
[11]	M. Gairing, B. Monien, and A. Woclaw, “A faster combinatorial approximation algorithm for scheduling unrelated machines,” Theoretical Computer Science, Vol. 380, pp. 87–99, 2007.