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 t , information on the first longest job arriving after t t is known. In this paper online  means that jobs arrive over time, J?(t) J ? ( t ) denotes the first longest job arriving after t t , 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/2 3 / 2 , and show that any online algorithm cannot have a competitive ratio less than 3 3 ? 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.
online algorithm parallel batch scheduling competitive ratio information in advance