INFOR Information Systems and Operational Research · 1998 · 119 citations · 0 references
ManagementIndustrial EngineeringOperations ManagementOptimizationProduction PlanningSchedulingJob SchedulingMachine SchedulingMakespan MinimizationScheduling TheoryStochastic SchedulingDeteriorating JobsLower Bound ComputationLower Bound TechniquesMakespan OptimizationParallel Machine Makespan MinimizationTwo-machine Scheduling
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.