TY - JOUR
T1 - Scheduling time-dependent jobs under mixed deterioration
AU - Gawiejnowicz, Stanisław
AU - Lin, Miao-Tsong
PY - 2010/3/15
Y1 - 2010/3/15
N2 - 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.
AB - 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.
KW - Deteriorating jobs
KW - NP-hard problems
KW - Polynomial-time algorithms
KW - Scheduling
KW - Single machine
UR - http://www.scopus.com/inward/record.url?scp=77649237125&partnerID=8YFLogxK
U2 - 10.1016/j.amc.2010.01.037
DO - 10.1016/j.amc.2010.01.037
M3 - Article
AN - SCOPUS:77649237125
VL - 216
SP - 438
EP - 447
JO - Applied Mathematics and Computation
JF - Applied Mathematics and Computation
SN - 0096-3003
IS - 2
ER -