Scheduling stochastic jobs with asymmetric earliness and tardiness penalties

Scheduling stochastic jobs with asymmetric earliness and tardiness penalties

0.00 Avg rating0 Votes
Article ID: iaor19981170
Country: United States
Volume: 44
Issue: 6
Start Page Number: 531
End Page Number: 557
Publication Date: Sep 1997
Journal: Naval Research Logistics
Authors: ,
Abstract:

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 pseudo-polynomial 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.

Reviews

Required fields are marked *. Your email address will not be published.