TY - JOUR

T1 - A note on "minimizing the maximum deviation of job completion time about a common due-date"

AU - Chhajed, Dilip

PY - 1988

Y1 - 1988

N2 - A recent paper by Cheng analyzed the problem of simultaneous determination of a common due-date and a sequence of n jobs to minimize the maximum deviation of job completion time around the common due-date. It is assumed that all jobs are available at time zero and their processing times, ti's, are known in advance. The analysis in Cheng used an LP formulation and duality results to prove the theorems. This note provides an alternate simpler proof for the same results. We also give some results for the case when splitting and preemption are allowed. A recent paper by Cheng [1] gives an optimal solution to the problem of setting a common due-date and sequence of n jobs on a single machine. All jobs are available at time zero and their processing times, ti's, are known in advance. The objective is to determine the optimal common due-date value k*, and the sequence ( σ ) to minimize the maximum deviation of job completion time about the common due-date. We here give a much simpler proof of the results derived in [1]. The notations used here are the same as in [1]. Let C[1] denote the completion time (decision variable) and t[i] denote the given processing time of a job in the ith position of sequence σ.

AB - A recent paper by Cheng analyzed the problem of simultaneous determination of a common due-date and a sequence of n jobs to minimize the maximum deviation of job completion time around the common due-date. It is assumed that all jobs are available at time zero and their processing times, ti's, are known in advance. The analysis in Cheng used an LP formulation and duality results to prove the theorems. This note provides an alternate simpler proof for the same results. We also give some results for the case when splitting and preemption are allowed. A recent paper by Cheng [1] gives an optimal solution to the problem of setting a common due-date and sequence of n jobs on a single machine. All jobs are available at time zero and their processing times, ti's, are known in advance. The objective is to determine the optimal common due-date value k*, and the sequence ( σ ) to minimize the maximum deviation of job completion time about the common due-date. We here give a much simpler proof of the results derived in [1]. The notations used here are the same as in [1]. Let C[1] denote the completion time (decision variable) and t[i] denote the given processing time of a job in the ith position of sequence σ.

UR - http://www.scopus.com/inward/record.url?scp=38249032498&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249032498&partnerID=8YFLogxK

U2 - 10.1016/0893-9659(88)90064-X

DO - 10.1016/0893-9659(88)90064-X

M3 - Article

AN - SCOPUS:38249032498

VL - 1

SP - 161

EP - 163

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

SN - 0893-9659

IS - 2

ER -