A linear time approximation scheme for minimizing total weighted completion time of unbounded batch scheduling

We study the unbounded batch machine scheduling of n jobs. A batch machine can handle up to B=n jobs simultaneously. Each job is characterized by a positive weight, a release time and a processing time. The processing time of a batch is the longest processing time among jobs in the batch. Jobs processed in the same batch have the same completion time, i.e., their common starting time plus the processing time of the batch. Our goal is to find a schedule for the jobs so that the total weighted completion is minimized. We present the first polynomial time approximation scheme that runs in linear time for any fixed accuracy.