GA Based Heuristic to Minimize Makespan in Single Machine Scheduling Problem with Uniform Parallel Machines

P. Senthilkumar, S. Narayanan

.

DOI: 10.4236/iim.2011.35025                

Abstract

This paper considers the single machine scheduling problem with uniform parallel machines in which the objective is to minimize the makespan. Four different GA based heuristics are designed by taking different combinations of crossover methods, viz. single point crossover method and two point crossover method, and job allocation methods while generating initial population, viz. equal number of jobs allocation to machines and proportionate number of jobs allocation to machines based on machine speeds. A detailed experiment has been conducted by assuming three factors, viz. Problem size, crossover method and job allocation method on 135 problem sizes each with two replications generated randomly. Finally, it is suggested to use the GA based heuristic with single point crossover method, in which the proportionate number of jobs allocated to machines based on machine speeds.

Keywords

Uniform Parallel Machines, Genetic Algorithm, Crossover Method, Job Allocation Method

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. Panneerselvam, “Production and Operations Management,” 2nd Edition, PHI Learning Private Limited, New Delhi, 2005.
[2]	P. Senthilkumar and S. Narayanan, “Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines,” Intelligent Information Management, Vol. 2, No. 8, 2010, pp. 457-474. doi:10.4236/iim.2010.28056
[3]	P. De and T. E. Morton, “Scheduling to Minimize Make- span on Unequal Parallel Processors,” Decision Sciences, Vol. 11, No. 4, 1980, pp. 586-602. doi:10.1111/j.1540-5915.1980.tb01163.x
[4]	R. L. Bulfin and R. G. Parker, “Scheduling Jobs on Two Facilities to Minimize Makespan,” Management Science, Vol. 26, No. 2, 1980, pp. 202-214. doi:10.1287/mnsc.26.2.202
[5]	D. K. Friesen and M. A. Langston, “Bounds for Multifit Scheduling on Uniform Proc-essors,” SIAM Journal on Computing, Vol. 12, No. 1, 1983, pp. 60-70. doi:10.1137/0212004
[6]	R. L. Graham, “Bounds for Multi-processing Timing Anomalies,” SIAM Journal of Applied Mathematics, Vol. 17, No. 2, 1969, pp.416-429. doi:10.1137/0117039
[7]	G. Dobson, “Scheduling Independ-ent Tasks on Uniform Processors,” SIAM Journal of Computing, Vol. 13, No. 4, 1984, pp. 705-716. doi:10.1137/0213044
[8]	D. K. Friesen, “Tighter Bounds for LPT Scheduling on Uniform Processors,” SIAM Journal on Computing, Vol. 16, No. 3, 1987, pp. 554-560. doi:10.1137/0216037
[9]	D. S. Hochbaum and D. B. Shmoys, “A Polynomial ApProximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Ap-proach,” SIAM Journal on Computing, Vol. 17, No. 3, 1988, pp. 539-551. doi:10.1137/0217033
[10]	B. Chen, “Parametric Bounds for LPT Scheduling on Uniform Processors,” Acta Mathematicae Applicateae Sinica, Vol. 7, No. 1, 1991, pp. 67-73. doi:10.1007/BF02080204
[11]	P. Mireault, J. B. Orlin and R. V. Vohra, “A Parametric Worst Case Analysis of the LPT Heu-ristic for Two Uniform Machines,” Operations Research, Vol. 45, No. 1, 1997, pp. 116-125. doi:10.1287/opre.45.1.116
[12]	R. E. Burkard and Y. He, “A Note on MULTIFIT Scheduling for Uniform Machines,” Computing, Vol. 61, No. 3, 1998, pp. 277-283. doi:10.1007/BF02684354
[13]	R. E. Burkard, Y. He and H. Kellerer, “A Linear Compound Algorithm for Uniform Ma-chine Scheduling,” Computing, Vol. 61, No. 1, 1998, pp. 1-9.
[14]	R. Panneerselvam and S. Kanagalingam, “Modelling Parallel Processors with Different Processing Speeds of Single Machine Scheduling Problem to Minimize Makespan,” Indus-trial Engineering Journal, Vol. 17, No. 6, 1998, pp. 16-19.
[15]	R. Panneerselvam and S. Kanagalingam, “Simple Heuristic for Single Machine Scheduling Problem with Two Parallel Processors Having Varying Speeds to Minimize Makespan,” Industrial Engineering Journal, Vol. 18, No. 6, 1999, pp. 2-8.
[16]	A. Agarwal, S. Colak, V. S. Jacob and H. Pirkul, “Heuristics and Augmented Neural Networks for Task Scheduling with Non-identical Machines,” European Journal of Operational Research, Vol. 175, No. 1, 2006, pp. 296- 317. doi:10.1016/j.ejor.2005.03.045
[17]	P. Senthilkumar and S. Narayanan, “Simulated Annealing Algorithm to Minimize Makespan in Single Machine Scheduling Problem with Uni-form Parallel Machines,” Intelligent Information Management, Vol. 3, No. 1, 2011, pp. 22-31. doi:10.4236/iim.2011.31003
[18]	C. Mihaila and A. Mihaila, “An Evolutionary Algorithm for Uniform Parallel Machines Scheduling,” 2nd UKSIM European Symposium on Computer Modelling and Simulation, Liverpool, 8-10 September 2008, pp. 76-80. doi:10.1109/EMS.2008.34
[19]	A. Mihaila and C. Mihaila, “Uniform Parallel Machines Scheduling Using a Genetic Algo-rithm,” 8th International Conference on Intelligent Systems Design and Applications, Kaohsiung, 26-28 November 2008, pp. 401-406.
[20]	R. Panneerselvam, “Design and Analysis of Algorithms,” PHI Learning Private Limited, New Delhi, 2007.
[21]	R. Panneerselvam, “Research Methodology,” PHI Learning Private Limited, New Delhi, 2004.