Abstract
We consider online scheduling on m parallel-batch machines where the batch capacity is unbounded and the jobs belong to m incompatible job families. By incompatible job families, we mean that jobs from different families cannot be processed together in the same batch. The processing time of a job becomes known only upon its arrival. The objective is to minimize the makespan. The problem is difficult to solve so we consider the case where the number of families is equal to the number of machines. We give a lower bound 5+12≈1.618 on the competitive ratio of any online algorithm for this restricted problem. We also provide an online algorithmHm(θ), where θ∈(0,1) is a parameter, and show that its competitive ratio is no less than 1+105≈1.632. When m=2 or under the condition that jobs belonging to the same family have identical processing times, we show thatHm(α), where α=5-12, is a best possible online algorithm. When m<3, we prove thatHm(β), where β=2-1, has a competitive ratio no greater than 1+1β+1≈1.707.
Original language | English |
---|---|
Pages (from-to) | 2380-2386 |
Number of pages | 7 |
Journal | Theoretical Computer Science |
Volume | 412 |
Issue number | 22 |
DOIs | |
Publication status | Published - 13 May 2011 |
Keywords
- Competitive ratio
- Incompatible job families
- Online scheduling
- Parallel-batch machines
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)