Reactive GRASP applied to task scheduling in parallel machines with sequence-dependent and resource-based setup times
Abstract
This work deals with the parallel machine scheduling problem with resource-assignable sequence dependent setup times. The goal of the problem is to minimize the total completion time and the total assignes resources. Due to the combinatorial complexity of this problem, an algorithm based on heuristic GRASP is proposed, in which the randomness parameter used in the construction phase is self-adjusted, according to the quality of the solutions previously found (Reactive GRASP). The obtained results are compared with the best results available in literature and show the good performance of the proposed algorithm.
References
Aiex, R.M., Binato, S. e Resende, M.G.C. (2003), “Parallel GRASP with path-relinking for job shop scheduling”. Parallel Computing, 29:393–430.
Armentano, V.A. e Yamashita, D.S. (2000), “Tabu search for scheduling on identical parallel machines to minimize mean tardiness”. J Intell Manuf. 11:453–460.
Feo, T.A. e Resende, M.G.C. (1995), “Greedy randomized adaptive search procedures”. Journal of Global Optimization, 6, 109-133.
Feo, T.A., Sarathy, K. e McGahan, J. (1996), “A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties”. Computers & Operations Research, 23:881-895.
Guinet, A. (1991), “Textile production systems: a sucession of non-identical parallel processor shops”. Journal of the Operational Research Society, 42(8): 655-671.
Kim, D-W., Kim, K-H, Jang, W. e Chen, F.F.(2002), “Unrelated parallel machine scheduling with setup times using simulated annealing”. Robotics and Computer Integrated Manufacturing, 18: 223-231.
Marsh, J.D. e Montgomery, D.C. (1973), “Optimal procedures for scheduling Jobs with sequence-dependent changeover times on parallel processors”. AIIE Technical Papers, 279-286.
Prais, M. e Ribeiro, C. (2000), “Reactive GRASP: na application to a matrix decomposition problem in TDMA traffic assignment”. INFORMS Journal on Computing, 12(3):164-176.
Ruiz, R. e Andrés, C. (2006), “Unrelated parallel machines scheduling with resource-assignable sequence dependent setup times”. MISTA Conference, 3, 439-446.
Armentano, V.A. e Yamashita, D.S. (2000), “Tabu search for scheduling on identical parallel machines to minimize mean tardiness”. J Intell Manuf. 11:453–460.
Feo, T.A. e Resende, M.G.C. (1995), “Greedy randomized adaptive search procedures”. Journal of Global Optimization, 6, 109-133.
Feo, T.A., Sarathy, K. e McGahan, J. (1996), “A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties”. Computers & Operations Research, 23:881-895.
Guinet, A. (1991), “Textile production systems: a sucession of non-identical parallel processor shops”. Journal of the Operational Research Society, 42(8): 655-671.
Kim, D-W., Kim, K-H, Jang, W. e Chen, F.F.(2002), “Unrelated parallel machine scheduling with setup times using simulated annealing”. Robotics and Computer Integrated Manufacturing, 18: 223-231.
Marsh, J.D. e Montgomery, D.C. (1973), “Optimal procedures for scheduling Jobs with sequence-dependent changeover times on parallel processors”. AIIE Technical Papers, 279-286.
Prais, M. e Ribeiro, C. (2000), “Reactive GRASP: na application to a matrix decomposition problem in TDMA traffic assignment”. INFORMS Journal on Computing, 12(3):164-176.
Ruiz, R. e Andrés, C. (2006), “Unrelated parallel machines scheduling with resource-assignable sequence dependent setup times”. MISTA Conference, 3, 439-446.
Published
2009-07-20
How to Cite
KAMPKE, Edmar Hell; ARROYO, José Elias Cláudio; ROCHA, Mauro Nacif.
Reactive GRASP applied to task scheduling in parallel machines with sequence-dependent and resource-based setup times. In: NATIONAL MEETING ON ARTIFICIAL AND COMPUTATIONAL INTELLIGENCE (ENIAC), 7. , 2009, Bento Gonçalves/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 222-231.
ISSN 2763-9061.
