An Online Scheduling Problem on a Drop-Line Parallel Batch Machine with Delivery Times and Limited Restart

Hailing Liu and Xiwen Lu
Additional contact information
Hailing Liu: Department of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China2College of Science, Henan University of Engineering, Zhengzhou 451191, Henan, P. R. China
Xiwen Lu: Department of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 06, 1-26

Abstract: This paper studies online scheduling on an unbounded drop-line parallel batch machine with delivery times and limited restarts. A drop-line parallel batch machine is a system that can process some jobs simultaneously as a batch. Jobs in a batch have the same starting time and the completion time of a job is equal to its starting time plus its processing time. Limited restarts mean that a running batch containing at least one restarted job cannot be restarted again. The objective is to minimize the time by which all jobs have been delivered. We prove that any online algorithm has a competitive ratio of at least 1 + α, where α(α ≈ 0.5188) is the positive solution of the equation x(x + x2 + x3 + 1) = 1. We provide a best possible (1 + α)-competitive online algorithm for the problem. Furthermore, we study the restricted problem with small delivery times and provide a best possible online algorithm with a competitive ratio of 3 2.

Keywords: Online scheduling; drop-line; parallel batch; limited restart; delivery (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595921500111
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:wsi:apjorx:v:38:y:2021:i:06:n:s0217595921500111

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595921500111

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().