Share This Article:

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

Abstract Full-Text HTML Download Download as PDF (Size:500KB) PP. 188-198
DOI: 10.4236/iim.2012.23022    5,574 Downloads   10,860 Views   Citations

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

P. Sivasankaran, T. Sornakumar and R. Panneerselvam, "Efficient Heuristic to Minimize Makespan in Single Machine Scheduling Problem with Unrelated Parallel Machines," Intelligent Information Management, Vol. 2 No. 3, 2010, pp. 188-198. doi: 10.4236/iim.2012.23022.

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.

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.