An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities

Ruyan Fu, Ji Tian, Shisheng Li and Jinjiang Yuan ()
Additional contact information
Ruyan Fu: China University of Mining and Technology
Ji Tian: China University of Mining and Technology
Shisheng Li: Zhongyuan University of Technology
Jinjiang Yuan: Zhengzhou University

Journal of Combinatorial Optimization, 2017, vol. 34, issue 4, No 12, 1187-1197

Abstract: Abstract We consider the online (over time) scheduling on a single unbounded parallel-batch machine with job processing time compatibilities to minimize makespan. In the problem, a constant $$\alpha >0$$ α > 0 is given in advance. Each job $$J_{j}$$ J j has a normal processing time $$p_j$$ p j . Two jobs $$J_i$$ J i and $$J_j$$ J j are compatible if $$\max \{p_i, p_j\} \le (1+\alpha )\cdot \min \{p_i, p_j\}$$ max { p i , p j } ≤ ( 1 + α ) · min { p i , p j } . In the problem, mutually compatible jobs can form a batch being processed on the machine. The processing time of a batch is equal to the maximum normal processing time of the jobs in this batch. For this problem, we provide an optimal online algorithm with a competitive ratio of $$1+\beta _\alpha $$ 1 + β α , where $$\beta _\alpha $$ β α is the positive root of the equation $$(1+\alpha )x^{2}+\alpha x=1+\alpha $$ ( 1 + α ) x 2 + α x = 1 + α .

Keywords: Online scheduling; Batch machine; Compatibility; Competitive ratio (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0139-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:34:y:2017:i:4:d:10.1007_s10878-017-0139-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0139-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().