On-line scheduling with equal-length jobs on parallel-batch machines to minimise maximum flow-time with delivery times

Ran Lin, Wenhua Li and Xing Chai

Journal of the Operational Research Society, 2021, vol. 72, issue 8, 1754-1761

Abstract: We consider on-line scheduling on m parallel-batch machines with equal-length jobs. The jobs arrive over time and the goal is to minimise the maximum flow-time with delivery times. When the capacity of each batch is unbounded, we provide a best possible on-line algorithm of competitive ratio 1+αm, where αm is the positive root of x2+mx=1. When the capacity of each batch is bounded, we provide a best possible on-line algorithm of competitive ratio 5+12. For the non-batch model, i.e., the capacity of each batch is 1, we provide a best possible on-line algorithm of competitive ratio 2 for m = 1 and an on-line algorithm of competitive ratio 32 for m≥2.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1578626 (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:tjorxx:v:72:y:2021:i:8:p:1754-1761

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

DOI: 10.1080/01605682.2019.1578626

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().