Design and Comparison of Simulated Annealing Algorithm and GRASP to Minimize Makespan in Single Machine Scheduling with Unrelated Parallel Machines
ABSTRACT
This paper discusses design and comparison of Simulated Annealing Algorithm and Greedy Randomized Adaptive Search Procedure (GRASP) to minimize the makespan in scheduling n single operation independent jobs on m unrelated parallel machines. This problem of minimizing the makespan in single machine scheduling problem with uniform parallel machines is NP hard. Hence, heuristic development for such problem is highly inevitable. In this paper, two different Meta-heuristics to minimize the makespan of the assumed problem are designed and they are compared in terms of their solutions. In the first phase, the simulated annealing algorithm is presented and then GRASP (Greedy Randomized Adaptive Search procedure) is presented to minimize the makespan in the single machine scheduling problem with unrelated parallel machines. It is found that the simulated annealing algorithm performs better than GRASP.
This paper discusses design and comparison of Simulated Annealing Algorithm and Greedy Randomized Adaptive Search Procedure (GRASP) to minimize the makespan in scheduling n single operation independent jobs on m unrelated parallel machines. This problem of minimizing the makespan in single machine scheduling problem with uniform parallel machines is NP hard. Hence, heuristic development for such problem is highly inevitable. In this paper, two different Meta-heuristics to minimize the makespan of the assumed problem are designed and they are compared in terms of their solutions. In the first phase, the simulated annealing algorithm is presented and then GRASP (Greedy Randomized Adaptive Search procedure) is presented to minimize the makespan in the single machine scheduling problem with unrelated parallel machines. It is found that the simulated annealing algorithm performs better than GRASP.
KEYWORDS
Makespan, Simulated Annealing Algorithm, GRASP, Unrelated Parallel Machines, Mathematical Model
Makespan, Simulated Annealing Algorithm, GRASP, Unrelated Parallel Machines, Mathematical Model
Cite this paper
nullP. Sivasankaran, T. Sornakumar and R. Panneerselvam, "Design and Comparison of Simulated Annealing Algorithm and GRASP to Minimize Makespan in Single Machine Scheduling with Unrelated Parallel Machines," Intelligent Information Management, Vol. 2 No. 7, 2010, pp. 406-416. doi: 10.4236/iim.2010.27050.
nullP. Sivasankaran, T. Sornakumar and R. Panneerselvam, "Design and Comparison of Simulated Annealing Algorithm and GRASP to Minimize Makespan in Single Machine Scheduling with Unrelated Parallel Machines," Intelligent Information Management, Vol. 2 No. 7, 2010, pp. 406-416. doi: 10.4236/iim.2010.27050.
References
[1] R. Panneerselvam, “Production and Operations Management,” 2nd Edition, PHI Learning Private Limited, New Delhi, 2005. [2] R. Panneerselvam, “Design and Analysis of Algorithms,” PHI Learning Private Limited, New Delhi, 2007. [3] E. L. Lawler and J. Labetoulle, “On Preemptive Scheduling on Unrelated Parallel Processors by Linear Programming,” Journal of the ACM, Vol. 25, No. 4, 1978, pp. 612-619. [4] C. N. Potts, “Analysis of a Linear Programming Heuristic for Scheduling Unrelated Parallel Machines,” Discrete Applied Mathematics, Vol. 10, No. 2, 1985, pp. 155-164. [5] S. L. Van De Velde, “Duality-Based Algorithms for Scheduling Unrelated Parallel Machines,” ORSA Journal of Computing, Vol. 5, No. 2, 1993, pp. 182-205. [6] C. A. Glass, C. N. Potts and P. Shade, “Unrelated Parallel Machine Scheduling Using Local Search,” Mathematical and Computer Modelling, Vol. 20, No. 2, 1994, pp. 41-52. [7] A. M. A. Hariri and C. N. Potts, “Heuristics for Scheduling Unrelated Parallel Machines,” Computers and Operations Research, Vol. 18, No. 3, 1991, pp. 323-331. [8] N. Piersman and W. Van Dijk, “A Local Search Heuristic for Unrelated Parallel Machine Scheduling with Efficient Neighbourhood Search,” Mathematical and Computer Modelling, Vol. 24, No. 9, 1996, pp. 11-19. [9] S. Martello, F. Soumis and P. Toth, “Exact and Approximation Algorithms for Makepsan Minimization on Unrelated Parallel Machines,” Discrete Applied Mathematics, Vol. 75, No. 2, 1997, pp. 169-188. [10] J. Klaus and P. Lorant, “Improved Approximation Schemes for Scheduling Unrelated Parallel Machines,” Mathematics of Operations Research, Vol. 26, No. 2, 2001, pp. 324-338. [11] F. Sourd, “Scheduling Tasks on Unrelated Machines: Large Neighbourhood Improvement Procedures,” Journal of Heuristics, Vol. 7, No. 6, 2001, pp. 519-531. [12] M. Serna and F. Xhafa, “Approximating Scheduling Unrelated Parallel Machines in Parallel,” Computational Optimization and Applications, Vol. 21, No. 3, 2002, pp. 325-338. [13] E. Mokotoff and P. Chretienne, “A Cutting Plane Algorithm for the Unrelated Parallel Machine Scheduling Problem,” European Journal of Operational Research, Vol. 141, No. 3, 2002, pp. 515-525. [14] E. Mokotoff and J. L. Jimeno, “Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem,” Annals of Operations Research, Vol. 117, No. 1-4, 2002, pp. 133-150. [15] M. Pfund, J. W. Fowlwr and J. N. D. Gupta, “A Survey of Algorithms for Single Machine and Multi-Objective Unrelated Parallel-Machine Deterministic Scheduling Pro- blems,” Journal of the Chinese Institute of Industrial Engineers, Vol. 21, No. 3, 2004, pp. 230-241. [16] M. Ghirardi and C. N. Potts, “Makespan Minimization for Scheduling Unrelated Parallel Machines: A Recovering Beam Search Approach,” European Journal of Operational Research, Vol. 165, No. 2, 2005, pp. 457-467. [17] E. V. Shchepin and N. Vakhania, “An Optimal Rounding Gives a Better Approximation for Scheduling Unrelated Machines,” Operations Research Letters, Vol. 33, No. 2, 2005, pp. 127-133. [18] B. Monien and A. Woclaw, “Scheduling Unrelated Parallel Machines Computational Results,” Proceedings of the 5th International Workshop on Experimental Algorithms, Menorca, Spain, 2006, pp. 195-206. [19] P. S. Efraimidis and P. G. Spirakis, “Approximation Schemes for Scheduling and Covering on Unrelated Machines,” Theoretical Computer Science, Vol. 359, No. 1, 2006, pp. 400-417. [20] M. Gairing, B. Monien and A. Woclaw, “A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Machines,” Theoretical Computer Science, Vol. 380, No. 1-2, 2007, pp. 87-99. [21] G. Christodoulou, E. Koutsoupias and A. Vidali, “A Lower Bound for Scheduling Mechanisms,” Algorithmica, Vol. 55, No. 4, 2009, pp. 729-740. [22] S. Kirkpatrick, Jr. C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, 1983, pp. 671-680. [23] T. A. Feo and M. G. C. Resende, “Greedy Randomized Adaptive Search Procedures,” Journal of Global Optimization, Vol. 6, No. 2, 1995, pp. 109-133. [24] R. Panneerselvam, “Research Methodology,” PHI Learning Private Limited, New Delhi, 2004.
[1] R. Panneerselvam, “Production and Operations Management,” 2nd Edition, PHI Learning Private Limited, New Delhi, 2005. [2] R. Panneerselvam, “Design and Analysis of Algorithms,” PHI Learning Private Limited, New Delhi, 2007. [3] E. L. Lawler and J. Labetoulle, “On Preemptive Scheduling on Unrelated Parallel Processors by Linear Programming,” Journal of the ACM, Vol. 25, No. 4, 1978, pp. 612-619. [4] C. N. Potts, “Analysis of a Linear Programming Heuristic for Scheduling Unrelated Parallel Machines,” Discrete Applied Mathematics, Vol. 10, No. 2, 1985, pp. 155-164. [5] S. L. Van De Velde, “Duality-Based Algorithms for Scheduling Unrelated Parallel Machines,” ORSA Journal of Computing, Vol. 5, No. 2, 1993, pp. 182-205. [6] C. A. Glass, C. N. Potts and P. Shade, “Unrelated Parallel Machine Scheduling Using Local Search,” Mathematical and Computer Modelling, Vol. 20, No. 2, 1994, pp. 41-52. [7] A. M. A. Hariri and C. N. Potts, “Heuristics for Scheduling Unrelated Parallel Machines,” Computers and Operations Research, Vol. 18, No. 3, 1991, pp. 323-331. [8] N. Piersman and W. Van Dijk, “A Local Search Heuristic for Unrelated Parallel Machine Scheduling with Efficient Neighbourhood Search,” Mathematical and Computer Modelling, Vol. 24, No. 9, 1996, pp. 11-19. [9] S. Martello, F. Soumis and P. Toth, “Exact and Approximation Algorithms for Makepsan Minimization on Unrelated Parallel Machines,” Discrete Applied Mathematics, Vol. 75, No. 2, 1997, pp. 169-188. [10] J. Klaus and P. Lorant, “Improved Approximation Schemes for Scheduling Unrelated Parallel Machines,” Mathematics of Operations Research, Vol. 26, No. 2, 2001, pp. 324-338. [11] F. Sourd, “Scheduling Tasks on Unrelated Machines: Large Neighbourhood Improvement Procedures,” Journal of Heuristics, Vol. 7, No. 6, 2001, pp. 519-531. [12] M. Serna and F. Xhafa, “Approximating Scheduling Unrelated Parallel Machines in Parallel,” Computational Optimization and Applications, Vol. 21, No. 3, 2002, pp. 325-338. [13] E. Mokotoff and P. Chretienne, “A Cutting Plane Algorithm for the Unrelated Parallel Machine Scheduling Problem,” European Journal of Operational Research, Vol. 141, No. 3, 2002, pp. 515-525. [14] E. Mokotoff and J. L. Jimeno, “Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem,” Annals of Operations Research, Vol. 117, No. 1-4, 2002, pp. 133-150. [15] M. Pfund, J. W. Fowlwr and J. N. D. Gupta, “A Survey of Algorithms for Single Machine and Multi-Objective Unrelated Parallel-Machine Deterministic Scheduling Pro- blems,” Journal of the Chinese Institute of Industrial Engineers, Vol. 21, No. 3, 2004, pp. 230-241. [16] M. Ghirardi and C. N. Potts, “Makespan Minimization for Scheduling Unrelated Parallel Machines: A Recovering Beam Search Approach,” European Journal of Operational Research, Vol. 165, No. 2, 2005, pp. 457-467. [17] E. V. Shchepin and N. Vakhania, “An Optimal Rounding Gives a Better Approximation for Scheduling Unrelated Machines,” Operations Research Letters, Vol. 33, No. 2, 2005, pp. 127-133. [18] B. Monien and A. Woclaw, “Scheduling Unrelated Parallel Machines Computational Results,” Proceedings of the 5th International Workshop on Experimental Algorithms, Menorca, Spain, 2006, pp. 195-206. [19] P. S. Efraimidis and P. G. Spirakis, “Approximation Schemes for Scheduling and Covering on Unrelated Machines,” Theoretical Computer Science, Vol. 359, No. 1, 2006, pp. 400-417. [20] M. Gairing, B. Monien and A. Woclaw, “A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Machines,” Theoretical Computer Science, Vol. 380, No. 1-2, 2007, pp. 87-99. [21] G. Christodoulou, E. Koutsoupias and A. Vidali, “A Lower Bound for Scheduling Mechanisms,” Algorithmica, Vol. 55, No. 4, 2009, pp. 729-740. [22] S. Kirkpatrick, Jr. C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, 1983, pp. 671-680. [23] T. A. Feo and M. G. C. Resende, “Greedy Randomized Adaptive Search Procedures,” Journal of Global Optimization, Vol. 6, No. 2, 1995, pp. 109-133. [24] R. Panneerselvam, “Research Methodology,” PHI Learning Private Limited, New Delhi, 2004.