Panneerselvam Senthilkumar, Sockalingam Narayanan

Abstract: This paper presents a simulated annealing algorithm to minimize makespan of single machine scheduling problem with uniform parallel machines. The single machine scheduling problem with uniform parallel machines consists of n jobs, each with single operation, which are to be scheduled on m parallel machines with different speeds. Since, this scheduling problem is a combinatorial problem; usage of a heuristic is inevitable to obtain the solution in polynomial time. In this paper, simulated annealing algorithm is presented. In the first phase, a seed generation algorithm is given. Then, it is followed by three variations of the simulated annealing algorithms and their comparison using ANOVA in terms of their solutions on makespan.

Keywords: Uniform Parallel Machines, Measure of Performance, Heuristic, Simulated Annealing Algorithm, ANOVA

Cite this paper: nullP. Senthilkumar and S. Narayanan, "Simulated Annealing Algorithm to Minimize Makespanin Single Machine Scheduling Problem withUniform Parallel Machines," Intelligent Information Management, Vol. 3 No. 1, 2011, pp. 22-31. doi: 10.4236/iim.2011.31003.

References

[1]   R. Panneerselvam, “Production and Operations Management,” 2nd Edition, Prentice-Hall of India, New Delhi, 2005.

[2]   E. Horowiz and S. Sahni, “Exact and Approximate Algorithms for Scheduling Nonidentical Processors,” Journal of the ACM, Vol. 23, No. 2, 1976, pp. 317-327. doi:10.1145/321941.321951

[3]   O. H. Ibarra and C. E. Kim, “Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors,” Journal of the ACM, Vol. 24, No. 2, 1977, pp. 280- 289. doi:10.1145/322003.322011

[4]   de Prabuddha and T. E. Morton, “Scheduling to Minimize Makespan on Unequal Parallel Processors,” Decision Sciences, Vol. 11, 1980, pp. 586-602. doi:10.1111/j.1540-5915.1980.tb01163.x

[5]   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

[6]   D. K. Friesen and M. A. Langston, “Bounds for Multifit Scheduling on Uniform Processors,” SIAM Journal on Computing, Vol. 12, 1983, pp. 60-70. doi:10.1137/0212004

[7]   R. L. Graham, “Bounds for Multiprocessing Timing Anomalies,” SIAM Journal of Applied Mathematics, Vol. 17, No. 2, 1969, pp. 416-429. doi:10.1137/0117039

[8]   G. Dobson, “Scheduling Independent Tasks on Uniform Processors,” SIAM Journal of Computing, Vol. 13, No. 4, 1984, pp. 705-716. doi:10.1137/0213044

[9]   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

[10]   D. S. Hochbaum and D. B. Shmoys, “A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach,” SIAM Journal on Computing, Vol. 17, No. 3, 1988, pp. 539-551. doi:10.1137/0217033

[11]   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

[12]   P. Mireault, J. B. Orlin and R. V. Vohra, “A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines,” Operations Research, Vol. 45, No. 1, 1997, pp. 116-125. doi:10.1287/opre.45.1.116

[13]   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

[14]   R. E. Burkard, Y. He and H. Kellerer, “A Linear Compound Algorithm for Uniform Machine Scheduling,” Computing, Vol. 61, No. 1, 1998, pp. 1-9. doi:10.1007/BF02684446

[15]   R. Panneerselvam and S. Kanagalingam, “Modelling Parallel Processors with Different Processing Speeds of Single Machine Scheduling Problem to Minimize Make- span,” Industrial Engineering Journal, Vol. 17, No. 6, 1998, pp. 16-19.

[16]   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.

[17]   C. Chekuri and M. Bender, “An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines,” Proceedings of IPCO’99, LNCS, 1999, pp. 383-393.

[18]   F. A. Chudak and D. B. Shmoys, “An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines,” Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997, pp. 581-590.

[19]   J. Jaffe, “Efficient Scheduling of Tasks without Full Use of Processor Resources,” Theoretical Computer Science, Vol. 26, No. 1, 1980, pp. 22-35.

[20]   C. Chekuri and M.Bender, “An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines,” Journal of Algorithms, Vol. 41, No. 2, 2001, pp. 212-224. doi:10.1006/jagm.2001.1184

[21]   J. L. Ching and C.-H. Lin, “Makespan Minimization for Two Uniform Parallel Machines,” International Journal of Production Economics, Vol. 84, No. 2, 2003, pp. 205- 213. doi:10.1016/S0925-5273(02)00427-9

[22]   C. Koulamas and G. J. Kyparisis, “Makespan Minimization on Uniform Parallel Machines with Release Times,” European Journal of Operational Research, Vol. 157, No. 3, 2004, pp. 262-266. doi:10.1016/S0377-2217(03)00243-1

[23]   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

[24]   C.-H. Lin and C.-J. Liao, “Makespan Minimization for Multiple Uniform Machines,” Computers & Industrial Engineering, Vol. 52, No. 4, 2007, pp. 404-413.