Multi-machine scheduling with linear deterioration

Multi-machine scheduling with linear deterioration

0.00 Avg rating0 Votes
Article ID: iaor19991765
Country: Canada
Volume: 36
Issue: 4
Start Page Number: 205
End Page Number: 214
Publication Date: Nov 1998
Journal: INFOR
Authors:
Keywords: heuristics
Abstract:

We study multi-machine makespan minimization of deteriorating jobs, i.e. jobs whose processing times are increasing functions of their starting times. We assume simple linear deterioration, and parallel identical machines. The problem is proven to be NP-hard even for two machines. A heuristic and lower bound are introduced and tested numerically. The heuristic is shown to be asymptotically optimal under very general conditions. We also study a non-conventional performance measure relevant to settings with deteriorating jobs, namely, minimum total load on all machines.

Reviews

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