Best semi-online algorithms for unbounded parallel batch scheduling

We consider semi-online scheduling of an unbounded parallel batch machine to minimize the makespan where, at the present time instant tt, information on the first longest job arriving after tt is known. In this paper online   means that jobs arrive over time, J∗(t)J∗(t) denotes the first longest job arriving after tt, and p∗(t)p∗(t) and r∗(t)r∗(t) denote the processing time and arrival time of J∗(t)J∗(t), respectively. Given information p∗(t)p∗(t), we present an online algorithm with a competitive ratio (5−5)/2≈1.382, and show that the algorithm is the best possible; furthermore, this algorithm generates at most two batches. This algorithm is also the best possible given information J∗(t)J∗(t). Given information r∗(t)r∗(t), we present an online algorithm with a competitive ratio 3/23/2, and show that any online algorithm cannot have a competitive ratio less than 33≈1.442; furthermore, this algorithm generates at most three batches. Given information r∗(t)r∗(t) with the restriction that an online algorithm generates at most two batches, we present an online algorithm with a competitive ratio (5+1)/2≈1.618, and show that the algorithm is the best possible.