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.
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
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
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
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
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
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
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
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
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.
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.
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
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
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
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.
