|標題:||Scheduling time-dependent jobs under mixed deterioration|
Lin, Bertrand M. T.
Department of Information Management and Finance
|關鍵字:||Scheduling;Single machine;Deteriorating jobs;Polynomial-time algorithms;NP-hard problems|
|摘要:||We consider a new model of time-dependent scheduling. A set of deteriorating jobs has to be processed on a single machine which is available starting from a non-zero time. The processing times of some jobs from this set are constant, while other ones are either proportional or linear functions of the job starting times. The applied criteria of schedule optimality include the maximum completion time, the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We delineate a sharp boundary between computationally easy and difficult problems, showing polynomially solvable and NP-hard cases. (C) 2010 Elsevier Inc. All rights reserved.|
|期刊:||APPLIED MATHEMATICS AND COMPUTATION|