Research ArticleOpen AccessGoogle Scholar indexed
Simulated Annealing Algorithm to Minimize Makespanin Single Machine Scheduling Problem withUniform Parallel Machines
- 1
- 2
Intelligent Information Management·Volume 03 (2011)·Pages 22–31·Published 29 January 2011·DOI10.4236/iim.2011.31003
Copy link · social · email
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.
KeywordsUniform Parallel MachinesMeasure of PerformanceHeuristicSimulated Annealing AlgorithmANOVA
- R. Panneerselvam, “Production and Operations Management,” 2nd Edition, Prentice-Hall of India, New Delhi, 2005.
- 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
- 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
- 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
- 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 Processors,” SIAM Journal on Computing, Vol. 12, 1983, pp. 60-70. doi:10.1137/0212004
- 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
- G. Dobson, “Scheduling Independent Tasks on Uniform Processors,” SIAM Journal of Computing, Vol. 13, No. 4, 1984, pp. 705-716. doi:10.1137/0213044
- 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 Approach,” SIAM Journal on Computing, Vol. 17, No. 3, 1988, pp. 539-551. doi:10.1137/0217033
- 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
- 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
- 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
- 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