Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times |
| |
Authors: | Pedro Leite Rocha Martín Gómez Ravetti Geraldo Robson Mateus Panos M Pardalos |
| |
Affiliation: | 1. Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Brazil;2. Department of Industrial and Systems Engineering, University of Florida, USA |
| |
Abstract: | A scheduling problem with unrelated parallel machines, sequence and machine-dependent setup times, due dates and weighted jobs is considered in this work. A branch-and-bound algorithm (B&B) is developed and a solution provided by the metaheuristic GRASP is used as an upper bound. We also propose a set of instances for this type of problem. The results are compared to the solutions provided by two mixed integer programming models (MIP) with the solver CPLEX 9.0. We carry out computational experiments and the algorithm performs extremely well on instances with up to 30 jobs. |
| |
Keywords: | Scheduling GRASP Branch-and-bound Sequence-dependent setups Machine-dependent setups Parallel machines |
本文献已被 ScienceDirect 等数据库收录! |