Randomized selection algorithm for online stochastic unrelated machines scheduling

Xiaoyan Zhang, Ran Ma, Jian Sun and Zan-Bo Zhang ()
Additional contact information
Xiaoyan Zhang: Nanjing Normal University
Ran Ma: Qingdao University of Technology
Jian Sun: Beijing University of Technology
Zan-Bo Zhang: Guangdong University of Finance and Economics

Journal of Combinatorial Optimization, No 0, 16 pages

Abstract: Abstract We consider an online stochastic unrelated machines scheduling problem. Specifically, a set of jobs arriving online over time must be randomly scheduled on the unrelated machines, which implies that the information of each job, including the release date and the weight, is not known until it is released. Furthermore, the actual processing time of each job is disclosed upon completion of this job. In addition, we focus on unrelated machines, which means that each job has a processing speed on every machine. Our goal is to minimize the expected total weighted completion time of all jobs. In this paper, we present a randomized selection algorithm for this problem and prove that the competitive ratio is a constant. Moreover, we show that it is asymptotic optimal for the online stochastic uniform machines scheduling problem when some parameters are bounded. Moreover, our proof does not require any probabilistic assumption on the job parameters.

Keywords: Online scheduling; Unrelated machines; Randomized selection algorithm; Expected total weighted completion time (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00542-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v::y::i::d:10.1007_s10878-020-00542-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00542-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().