Online-List Scheduling on a Single Bounded Parallel-Batch Machine to Minimize Makespan

Wenhua Li (), Jie Gao and Jinjiang Yuan
Additional contact information
Wenhua Li: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, People's Republic of China
Jie Gao: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, People's Republic of China
Jinjiang Yuan: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, People's Republic of China

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 04, 1-15

Abstract: In this paper, we consider the online-list scheduling on a single bounded parallel-batch machine to minimize makespan. In the problem, the jobs arrive online over list. The first unassigned job in the list should be assigned to a batch before the next job is released. Each batch can accommodate up to b jobs. For b = 2, we establish a lower bound 1 + γ of competitive ratio and provide an online algorithm with a competitive ratio of $\frac{\sqrt{5}+1}{2}$, where γ is the positive root of γ(γ + 1)2 = 1. For b = 3, we establish a lower bound 1 + α of competitive ratio and provide an online algorithm with a competitive ratio of 2, where α is the positive root of the equation (1 + α)(1 + α2) = 2.

Keywords: Online-list scheduling; parallel batching; makespan; competitive ratio (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595915500281
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:32:y:2015:i:04:n:s0217595915500281

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595915500281

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 ().