Minimizing the Total Weighted Completion Time on Unrelated

Proceedings of the 2005 Winter Simulation Conference M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines, eds.

MINIMIZING THE TOTAL WEIGHTED COMPLETION TIME ON UNRELATED PARALLEL MACHINES WITH STOCHASTIC TIMES Jean-Paul M. Arnaout Ghaith Rabadi Engineering Management and Systems Engineering Department 247 Kaufman Hall Old Dominion University Norfolk, VA 23529, U.S.A.

ABSTRACT This paper addresses the problem of batch scheduling in an unrelated parallel machine environment with sequence dependent setup times and an objective of minimizing the weighted mean completion time. Identical jobs are batched together and are available at time zero. Processing time of each job of a batch is determined according to both the machine it will be assigned to and the batch group to which the job belongs. The jobs’ processing times and setup times are stochastic for better depiction of the real world. This is a NP-hard problem and in this paper, a solution heuristic is developed and compared to existing ones using simulation. The results and analysis obtained from the computational experiments proved the superiority of the proposed algorithm PMWP over the other algorithms presented. 1 INTRODUCTION

In this paper we compare different heuristics for the problem of scheduling a set of independent batches (each batch is a group of identical jobs) on a set of unrelated parallel machines. For several years now, there has been significant research involving scheduling in batches, as it may be cheaper and faster to process jobs in batches than to process them individually (Potts and Kovalyov 2000). One of the main benefits gained by batch scheduling is revealed in the case of setup times, where the machines incur setup times associated with processing different jobs; a lot of time can be saved by scheduling identical jobs in batches, as setup will only be performed when switching batches instead of individual jobs. There are two possible scenarios in batch scheduling...