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

Zhenpeng Li and Congdian Cheng ()
Additional contact information
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

Mathematics, 2023, vol. 11, issue 11, 1-12

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.

Keywords: single machine; single breakdown; schedule; flowtime; stochastic optimization; online optimization (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/11/2413/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/11/2413/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:11:p:2413-:d:1153357

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().