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

Dilip Chhajed

Research output: Contribution to journalArticlepeer-review

Abstract

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 σ.

Original languageEnglish (US)
Pages (from-to)161-163
Number of pages3
JournalApplied Mathematics Letters
Volume1
Issue number2
DOIs
StatePublished - 1988

ASJC Scopus subject areas

  • Applied Mathematics

Fingerprint Dive into the research topics of 'A note on "minimizing the maximum deviation of job completion time about a common due-date"'. Together they form a unique fingerprint.

Cite this