×

Stochastic scheduling subject to machine breakdowns: the preemptive-repeat model with discounted reward and other criteria. (English) Zbl 1075.90035

Summary: We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive-repeat model, which addresses the situation where, if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date-related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications.

MSC:

90B36 Stochastic scheduling theory in operations research
60E10 Characteristic functions; other transforms
90B25 Reliability, availability, maintenance, inspection in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adiri, Acta Inform 26 pp 679– (1989)
[2] Adiri, Naval Res Logist 38 pp 261– (1991)
[3] Bagga, J Inform Optim Sci 2 pp 103– (1981)
[4] Birge, Naval Res Logist 37 pp 661– (1990)
[5] Cai, Oper Res 47 pp 422– (1999)
[6] Cai, Ann Oper Res 98 pp 313– (2000)
[7] Cai, Probab Engrg Inf Sci 17 pp 467– (2003)
[8] Sequencing and scheduling: An introduction to the mathematics of the job-shop, Ellis Horwood, Chichester, 1982. · Zbl 0479.90037
[9] Frostig, Probab Engrg Inform Sci 5 pp 349– (1991)
[10] Mittenthal, Oper Res 41 pp 786– (1993)
[11] and Comparison methods for stochastic models and risks, Wiley, Chichester, 2002. · Zbl 0999.60002
[12] Pinedo, Probab Engrg Inform Sci 2 pp 41– (1988)
[13] Scheduling: Theory, algorithms, and systems, 2nd edition, Prentice Hall, Englewood Cliffs, NJ, 2002.
[14] Qi, Stochastic Anal Appl 18 pp 635– (2000)
[15] Rothkopf, Management Sci 12 pp 437– (1966)
[16] Rothkopf, Management Sci 12 pp 707– (1966)
[17] Rothkopf, Oper Res 32 pp 451– (1984)
[18] Townsend, Management Sci 24 pp 530– (1978)
[19] Zhou, Math Comput Modelling 26 pp 95– (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.