Stochastic scheduling on parallel machines subject to random breakdowns to minimize expected costs for earliness and tardy jobs
成果类型：
Article
署名作者：
Cai, XQ; Zhou, S
署名单位：
Chinese University of Hong Kong; Hong Kong Polytechnic University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.3.422
发表日期：
1999
页码：
422-437
关键词：
摘要：
This paper addresses a stochastic scheduling problem in which a set of independent jobs are to be processed by a number of identical parallel machines under a common deadline. Each job has a processing time, which is a random variable with an arbitrary distribution. Each machine is subject to stochastic breakdowns, which are characterized by a Poisson process. The deadline is an exponentially distributed random variable. The objective is to minimize the expected costs for earliness and tardiness, where the cost for an early job is a general function of its earliness while the cost for a tardy job is a fixed charge. Optimal policies are derived for cases where there is only a single machine or are multiple machines, the decision-maker can take a static policy or a dynamic policy, and job preemptions are allowed or forbidden. In contrast to their deterministic counterparts, which have been known to be NP-hard and are thus intractable from a computational point of view, we find that optimal solutions for many cases of the stochastic problem can be constructed analytically.