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 t, information on the first longest job arriving after t is known. In this paper online means that jobs arrive over time, J*(t) denotes the first longest job arriving after t, and p*(t) and r*(t) denote the processing time and arrival time of J*(t), respectively. Given information 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). Given information r*(t), we present an online algorithm with a competitive ratio 32, 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) 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.