Simulated Annealing Algorithm to Minimize Makespanin Single Machine Scheduling Problem withUniform Parallel Machines
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.
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
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.
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.
[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.