Premium
Scheduling stochastic jobs with asymmetric earliness and tardiness penalties
Author(s) -
Cai X.,
Zhou S.
Publication year - 1997
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199709)44:6<531::aid-nav2>3.0.co;2-4
Subject(s) - tardiness , scheduling (production processes) , exponential distribution , mathematical optimization , random variable , due date , computer science , exponential function , sequence (biology) , mathematics , job shop scheduling , statistics , queue , mathematical analysis , schedule , biology , genetics , operating system , programming language
We consider a stochastic counterpart of the well‐known earliness‐tardiness scheduling problem with a common due date, in which n stochastic jobs are to be processed on a single machine. The processing times of the jobs are independent and normally distributed random variables with known means and known variances that are proportional to the means. The due dates of the jobs are random variables following a common probability distribution. The objective is to minimize the expectation of a weighted combination of the earliness penalty, the tardiness penalty, and the flow‐time penalty. One of our main results is that an optimal sequence for the problem must be V‐shaped with respect to the mean processing times. Other characterizations of the optimal solution are also established. Two algorithms are proposed, which can generate optimal or near‐optimal solutions in pseudopolynomial time. The proposed algorithms are also extended to problems where processing times do not satisfy the assumption in the model above, and are evaluated when processing times follow different probability distributions, including general normal (without the proportional relation between variances and means), uniform, Laplace , and exponential . © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44, 531–557, 1997.