Title: Minimising earliness and tardiness on parallel machines with sequence-dependent setups

Authors: Ghazi M. Magableh, Scott J. Mason

Addresses: Department of Mechanical Engineering, Prince Faisal Technical College (PFTC), Al-Balqa' Applied University (BAU), Amman, Jordan. ' Department of Industrial Engineering, 4207 Bell Engineering Center, University of Arkansas, Fayetteville, AR 72701, USA

Abstract: In this paper, we present heuristics for minimising total earliness and tardiness on a group of identical, parallel machines subject to sequence-dependent setups. Each job has a potentially unique due date, processing time and/or ready time. Our approach generates an initial feasible schedule using new algorithms and a dispatching rule, and then employs a local search procedure to improve this initial schedule when possible. Experimental results demonstrate the viability of our approach over a wide range of problem instances to produce near-optimal solutions in practically acceptable computation times.

Keywords: earliness; tardiness; parallel machines; parallel machine scheduling; sequence-dependent setups; dispatching rules; due dates.

DOI: 10.1504/IJOR.2010.033103

International Journal of Operational Research, 2010 Vol.8 No.1, pp.42 - 61

Published online: 08 May 2010 *

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