Title: A scheduling problem with unrelated parallel machines and sequence dependent setups

Authors: M. Gomez Ravetti, Geraldo R. Mateus, Pedro L. Rocha, Panos M. Pardalos

Addresses: Department of Computer Science, Federal University of Minas Gerais, Av. Antonio Carlos 6627 – Predio do ICEx, 31270-010, Belo Horizonte, MG Brazil. ' Department of Computer Science, Federal University of Minas Gerais, Av. Antonio Carlos 6627 – Predio do ICEx, 31270-010, Belo Horizonte, MG Brazil. ' Department of Computer Science, Federal University of Minas Gerais, Av. Antonio Carlos 6627 – Predio do ICEx, 31270-010, Belo Horizonte, MG Brazil. ' Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, 32611, Gainesville, FL, USA

Abstract: This paper addresses a scheduling problem with unrelated parallel machines, sequence dependent setups and due dates. The problem is based on a real case and the objective is to minimise the sum of the makespan and the weighted delays. A mixed integer linear programming model is proposed and since the model considers realistic constraints, a metaheuristic based on GRASP is used as a solution method. Several versions of the metaheuristic are tested and multiple instances of the problem with different configurations are generated to test the solution quality and the computational performance.

Keywords: scheduling problems; parallel machines; sequence dependent setups; due dates; metaheuristics; GRASP; operational research.

DOI: 10.1504/IJOR.2007.014169

International Journal of Operational Research, 2007 Vol.2 No.4, pp.380 - 399

Published online: 24 Jun 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article