Online batch scheduling of equal-length jobs on two identical batch machines to maximise the number of early jobs

Wenjie Li and Shisheng Li

International Journal of Systems Science, 2015, vol. 46, issue 4, 652-661

Abstract: We study the online batch scheduling of equal-length jobs on two identical batch machines. Each batch machine can process up to b jobs simultaneously as a batch (where b is called the capacity of the machines). The goal is to determine a schedule that maximises the (weighted) number of early jobs. For the non-preemptive model, we first present an upper bound that depends on the machine capacity b, and then we provide a greedy online algorithm with a competitive ratio of 1/(b + 1). For the preemption-restart model with b = ∞, we first show that no online algorithm has a competitive ratio greater than 0.595, and then we design an online algorithm with a competitive ratio of 10-46$10-4\sqrt{6}$.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207721.2013.794904 (text/html)
Access to full text is restricted to subscribers.

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:taf:tsysxx:v:46:y:2015:i:4:p:652-661

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TSYS20

DOI: 10.1080/00207721.2013.794904

Access Statistics for this article

International Journal of Systems Science is currently edited by Visakan Kadirkamanathan

More articles in International Journal of Systems Science from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().