IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i11p2413-d1153357.html
   My bibliography  Save this article

The Expected Competitive Ratio on a Kind of Stochastic-Online Flowtime Scheduling with Machine Subject to an Uncertain Breakdown

Author

Listed:
  • Zhenpeng Li

    (School of Electronics and Information Engineering, Taizhou University, Linhai 317000, China)

  • Congdian Cheng

    (School of Intelligence Technology, Geely University of China, Chengdu 641400, China)

Abstract

We consider the problem of scheduling jobs on a single machine subject to an uncertain breakdown to minimize the flowtime. Assuming the machine is unavailable during the breakdown, the starting time of the breakdown is a random variable s with distribution function D ( s ) and the terminating time of the breakdown has no any other information; jobs are non-resumable. Under these assumptions and starting from the perspective of statistical optimization, we first establish the scheduling problem HSONRP, which contains deterministic information, stochastic information, and online information and then define the expected competitive ratio of an algorithm to find the optimized solution of the problem HSONRP. In addition, then, we propose and prove certain results on the expected competitive ratio of the SPT rule. In particular, we prove the expected competitive ratio of SPT rule is less than 1 + max { p i } 2 P when s is the uniform distribution on interval ( 0 , P ] , where p i is the processing time of job i , P = ∑ i = 1 n p i , and show that it is no more than 5 4 under a quite loose condition. Meanwhile, we also make some discussions about our studies. What we have performed will enrich and improve the research results on the area of scheduling to minimize flowtime and advance the development of online optimization and stochastic optimization.

Suggested Citation

  • 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.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:11:p:2413-:d:1153357
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/11/2413/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/11/2413/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Byung-Cheon Choi & Myoung-Ju Park, 2022. "Single-machine scheduling with resource-dependent processing times and multiple unavailability periods," Journal of Scheduling, Springer, vol. 25(2), pages 191-202, April.
    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. Shi-Sheng Li & Ren-Xia Chen, 2022. "Minimizing total weighted late work on a single-machine with non-availability intervals," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1330-1355, September.
    4. Kacem, Imed & Chu, Chengbin, 2008. "Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1080-1089, June.
    5. K. D. Glazebrook, 1984. "Scheduling stochastic jobs on a single machine subject to breakdowns," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 31(2), pages 251-264, June.
    6. Ji Tian & Yan Zhou & Ruyan Fu, 2020. "An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown," Journal of Combinatorial Optimization, Springer, vol. 40(1), pages 170-180, July.
    7. Breit, Joachim, 2007. "Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint," European Journal of Operational Research, Elsevier, vol. 183(2), pages 516-524, December.
    8. 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.
    9. Tsung-Chyan Lai & Yuri N. Sotskov & Natalja G. Egorova & Frank Werner, 2018. "The optimality box in uncertain data for minimising the sum of the weighted job completion times," International Journal of Production Research, Taylor & Francis Journals, vol. 56(19), pages 6336-6362, October.
    10. John Mittenthal & M. Raghavachari, 1993. "Stochastic Single Machine Scheduling with Quadratic Early-Tardy Penalties," Operations Research, INFORMS, vol. 41(4), pages 786-796, August.
    11. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    12. Sadfi, Cherif & Penz, Bernard & Rapine, Christophe & Blazewicz, Jacek & Formanowicz, Piotr, 2005. "An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints," European Journal of Operational Research, Elsevier, vol. 161(1), pages 3-10, February.
    Full references (including those not matched with items on IDEAS)

    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. Hanane Krim & Rachid Benmansour & David Duvivier & Daoud Aït-Kadi & Said Hanafi, 2020. "Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance," Computational Optimization and Applications, Springer, vol. 75(1), pages 291-320, January.
    2. Shabtay, Dvir & Zofi, Moshe, 2018. "Single machine scheduling with controllable processing times and an unavailability period to minimize the makespan," International Journal of Production Economics, Elsevier, vol. 198(C), pages 191-200.
    3. Hans Kellerer & Vitaly A. Strusevich, 2016. "Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications," Annals of Operations Research, Springer, vol. 240(1), pages 39-94, May.
    4. Kellerer, Hans & Kubzin, Mikhail A. & Strusevich, Vitaly A., 2009. "Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval," European Journal of Operational Research, Elsevier, vol. 199(1), pages 111-116, November.
    5. 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.
    6. Yunqiang Yin & Jianyou Xu & T. C. E. Cheng & Chin‐Chia Wu & Du‐Juan Wang, 2016. "Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 172-183, March.
    7. Shabtay, Dvir, 2022. "Single-machine scheduling with machine unavailability periods and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 296(2), pages 423-439.
    8. 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.
    9. 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.
    10. Yuri N. Sotskov & Natalja G. Egorova, 2019. "The Optimality Region for a Single-Machine Scheduling Problem with Bounded Durations of the Jobs and the Total Completion Time Objective," Mathematics, MDPI, vol. 7(5), pages 1-21, April.
    11. 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.
    12. Umar M. Al‐Turki & John Mittenthal & M. Raghavachari, 1996. "The single‐machine absolute‐deviation early‐tardy problem with random completion times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(4), pages 573-587, June.
    13. K. D. Glazebrook, 1992. "Single‐machine scheduling of stochastic jobs subject to deterioration or delay," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(5), pages 613-633, August.
    14. Yin, Yunqiang & Luo, Zunhao & Wang, Dujuan & Cheng, T.C.E., 2023. "Wasserstein distance‐based distributionally robust parallel‐machine scheduling," Omega, Elsevier, vol. 120(C).
    15. 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.
    16. 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.
    17. Jing Fan & Xiwen Lu, 2015. "Supply chain scheduling problem in the hospital with periodic working time on a single machine," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 892-905, November.
    18. Marieke Quant & Marc Meertens & Hans Reijnierse, 2008. "Processing games with shared interest," Annals of Operations Research, Springer, vol. 158(1), pages 219-228, February.
    19. José R. Correa & Maurice Queyranne, 2012. "Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(5), pages 384-395, August.
    20. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.

    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:gam:jmathe:v:11:y:2023:i:11:p:2413-:d:1153357. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.