On-line scheduling with equal-length jobs on parallel-batch machines to minimise maximum flow-time with delivery times. Issue 8 (3rd August 2021)

• Record Type: Journal Article
• Authors: Lin, Ran; Li, Wenhua; Chai, Xing
• Is Part Of: Journal of the Operational Research Society. Volume 72:Issue 8(2021)
• Page Start: 1754
• Page End: 1761
• Publication Date: 2021-08-03
• Subjects: On-line scheduling -- parallel-batch -- flow-time -- delivery time -- competitive ratio; Operations research -- Periodicals; 658.4034
• DOI: 10.1080/01605682.2019.1578626
• Languages: English
• ISSNs: 0160-5682

Abstract

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 x 2 + mx = 1 . When the capacity of each batch is bounded, we provide a best possible on-line algorithm of competitive ratio 5 + 1 2 . 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 3 2 for m ≥ 2 .