IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v57y2009i5p1236-1249.html
   My bibliography  Save this article

Stochastic Scheduling Subject to Preemptive-Repeat Breakdowns with Incomplete Information

Author

Listed:
  • Xiaoqiang Cai

    (Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong)

  • Xianyi Wu

    (Department of Statistics and Actuarial Science, East China Normal University, Shanghai 200241, China)

  • Xian Zhou

    (Department of Actuarial Studies, Macquarie University, Sydney, NSW 2109, Australia)

Abstract

This paper considers the problem of scheduling a set of jobs on a single machine subject to stochastic breakdowns with incomplete information on the probability distributions involved in the decision process. We focus on the preemptive-repeat discipline, under which a machine breakdown leads to the loss of the work done on the job being processed. The breakdown process of the machine is allowed to depend on the job it is processing. The processing times required to complete the jobs, and the machine uptimes and downtimes, are random variables with incomplete information on their probability distributions characterized by unknown parameters. We establish the preemptive-repeat model with incomplete information and investigate its probabilistic characteristics. We show that optimal static policies can be obtained for a wide range of performance measures, which are determined by the prior distributions of the unknown parameters. We derive optimal dynamic policies via Gittins indices represented by the posterior distributions, which are updated adaptively based on processing histories. Under appropriate conditions, the optimal dynamic policies can be calculated by one-step reward rates in a closed form. As a by-product, we also show that our incomplete information model subsumes the traditional preemptive-repeat models with complete information as extreme cases.

Suggested Citation

  • Xiaoqiang Cai & Xianyi Wu & Xian Zhou, 2009. "Stochastic Scheduling Subject to Preemptive-Repeat Breakdowns with Incomplete Information," Operations Research, INFORMS, vol. 57(5), pages 1236-1249, October.
    • Handle: RePEc:inm:oropre:v:57:y:2009:i:5:p:1236-1249
    DOI: 10.1287/opre.1080.0660
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0660
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1080.0660?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Hongtao Zhang & Stephen C. Graves, 1997. "Cyclic Scheduling in a Stochastic Environment," Operations Research, INFORMS, vol. 45(6), pages 894-903, December.
    2. J. Birge & J. B. G. Frenk & J. Mittenthal & A. H. G. Rinnooy Kan, 1990. "Single‐machine scheduling subject to stochastic breakdowns," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(5), pages 661-677, October.
    3. Xiaoqiang Cai & Xiaoqian Sun & Xian Zhou, 2004. "Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(6), pages 800-817, September.
    4. I. Adiri & E. Frostig & A. H. G. Rinnooy Kan, 1991. "Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(2), pages 261-271, April.
    5. Lee, Chung-Yee & Lin, Chen-Sin, 2001. "Single-machine scheduling with maintenance and repair rate-modifying activities," European Journal of Operational Research, Elsevier, vol. 135(3), pages 493-513, December.
    6. Xiaoqiang Cai & Sean Zhou, 1999. "Stochastic Scheduling on Parallel Machines Subject to Random Breakdowns to Minimize Expected Costs for Earliness and Tardy Jobs," Operations Research, INFORMS, vol. 47(3), pages 422-437, June.
    7. Harry Groenevelt & Liliane Pintelon & Abraham Seidmann, 1992. "Production Batching with Machine Breakdowns and Safety Stocks," Operations Research, INFORMS, vol. 40(5), pages 959-971, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shi, Xiutian & Shen, Houcai & Wu, Ting & Cheng, T.C.E., 2014. "Production planning and pricing policy in a make-to-stock system with uncertain demand subject to machine breakdowns," European Journal of Operational Research, Elsevier, vol. 238(1), pages 122-129.
    2. Dmitry Ivanov & Alexandre Dolgui & Boris Sokolov & Frank Werner, 2016. "Schedule robustness analysis with the help of attainable sets in continuous flow problem under capacity disruptions," International Journal of Production Research, Taylor & Francis Journals, vol. 54(11), pages 3397-3413, June.
    3. Li, Dong & Glazebrook, Kevin D., 2011. "A Bayesian approach to the triage problem with imperfect classification," European Journal of Operational Research, Elsevier, vol. 215(1), pages 169-180, November.
    4. Xiaoqiang Cai & Xianyi Wu & Xian Zhou, 2021. "Optimal unrestricted dynamic stochastic scheduling with partial losses of work due to breakdowns," Annals of Operations Research, Springer, vol. 298(1), pages 43-64, March.
    5. Creemers, Stefan, 2019. "The preemptive stochastic resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 238-247.
    6. Stefan Creemers, 2019. "The preemptive stochastic resource-constrained project scheduling problem," Post-Print hal-02992618, HAL.
    7. Dana G. Popescu & Pascale Crama, 2016. "Ad Revenue Optimization in Live Broadcasting," Management Science, INFORMS, vol. 62(4), pages 1145-1164, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Xiaoqiang Cai & Xianyi Wu & Xian Zhou, 2021. "Optimal unrestricted dynamic stochastic scheduling with partial losses of work due to breakdowns," Annals of Operations Research, Springer, vol. 298(1), pages 43-64, March.
    2. Xiaoqiang Cai & Xiaoqian Sun & Xian Zhou, 2004. "Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(6), pages 800-817, September.
    3. W J Chen, 2006. "Minimizing total flow time in the single-machine scheduling problem with periodic maintenance," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(4), pages 410-415, April.
    4. Chen, Wen-Jinn, 2009. "Minimizing number of tardy jobs on a single machine subject to periodic maintenance," Omega, Elsevier, vol. 37(3), pages 591-599, June.
    5. Yarlin Kuo & Zi‐Ann Chang, 2007. "Integrated production scheduling and preventive maintenance planning for a single machine under a cumulative damage failure process," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(6), pages 602-614, September.
    6. X. Cai & F. S. Tu, 1996. "Scheduling jobs with random processing times on a single machine subject to stochastic breakdowns to minimize early‐tardy penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(8), pages 1127-1146, December.
    7. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    8. Mohebbi, E., 2008. "A note on a production control model for a facility with limited storage capacity in a random environment," European Journal of Operational Research, Elsevier, vol. 190(2), pages 562-570, October.
    9. Scott Webster & Z. Kevin Weng, 2001. "Improving Repetitive Manufacturing Systems: Model and Insights," Operations Research, INFORMS, vol. 49(1), pages 99-106, February.
    10. Lodree Jr., Emmett J. & Geiger, Christopher D., 2010. "A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration," European Journal of Operational Research, Elsevier, vol. 201(2), pages 644-648, March.
    11. Kazaz, Burak & Sloan, Thomas W., 2013. "The impact of process deterioration on production and maintenance policies," European Journal of Operational Research, Elsevier, vol. 227(1), pages 88-100.
    12. Om Prakash & A.R. Roy & A. Goswami, 2014. "Stochastic manufacturing system with process deterioration and machine breakdown," International Journal of Systems Science, Taylor & Francis Journals, vol. 45(12), pages 2539-2551, December.
    13. Peymankar, Mahboobe & Dehghanian, Farzad & Ghiami, Yousef & Abolbashari, Mohammad Hassan, 2018. "The effects of contractual agreements on the economic production quantity model with machine breakdown," International Journal of Production Economics, Elsevier, vol. 201(C), pages 203-215.
    14. Zhenpeng Li & Congdian Cheng, 2023. "The Expected Competitive Ratio on a Kind of Stochastic-Online Flowtime Scheduling with Machine Subject to an Uncertain Breakdown," Mathematics, MDPI, vol. 11(11), pages 1-12, May.
    15. Bouslah, Bassem & Gharbi, Ali & Pellerin, Robert, 2013. "Joint optimal lot sizing and production control policy in an unreliable and imperfect manufacturing system," International Journal of Production Economics, Elsevier, vol. 144(1), pages 143-156.
    16. Ali Allahverdi & John Mittenthal, 1994. "Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(5), pages 677-682, August.
    17. Xinyu Sun & Tao Liu & Xin-Na Geng & Yang Hu & Jing-Xiao Xu, 2023. "Optimization of scheduling problems with deterioration effects and an optional maintenance activity," Journal of Scheduling, Springer, vol. 26(3), pages 251-266, June.
    18. Wan, Guohua & Yen, Benjamin P.-C., 2009. "Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 195(1), pages 89-97, May.
    19. Sid Browne & Kevin D. Glazebrook, 1996. "Scheduling jobs that are subject to failure propagation," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(2), pages 265-288, March.
    20. Wolter, Anja & Helber, Stefan, 2013. "Simultaneous Production and Maintenance Planning for a Single Capacitated Resource facing both a Dynamic Demand and Intensive Wear and Tear," Hannover Economic Papers (HEP) dp-522, Leibniz Universität Hannover, Wirtschaftswissenschaftliche Fakultät.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:57:y:2009:i:5:p:1236-1249. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.