Parallel machines scheduling with machine maintenance for minsum criteria

Parallel machines scheduling with machine maintenance for minsum criteria

0.00 Avg rating0 Votes
Article ID: iaor20133340
Volume: 212
Issue: 2
Start Page Number: 287
End Page Number: 292
Publication Date: Jul 2011
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

This paper considers a parallel‐machine scheduling problem with machine maintenance. There are unavailable periods on each of the first k machines, and the remaining mk machines are always available, where 1⩽ km is an integer. The objective is to minimize the total completion time of all jobs. We show the classical SPT algorithm has a worst‐case ratio of at most 1 + m 1 m k equ1 when k < m. If there is exactly one unavailable period on each of the first k machines, and the unavailable periods do not overlap, the worst‐case ratio of SPT is at most 2 + k 1 m 1 equ2, and no polynomial time approximation algorithm with worst‐case ratio less than m m 1 equ3 can exist when k = m unless P = NP.

Reviews

Required fields are marked *. Your email address will not be published.