Abstract

Research focuses on the problem of scheduling a fixed number in batching machines. In this problem, n jobs and m (m is fixed) identical batching machines are given. Each job is characterized by a release time and a processing time. Every batching machine can process up to B(B<n) jobs as a batch simultaneously. The processing time of a batch is equal to the longest processing time among all 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. A polynomial time approximation scheme (PTAS) for this problem is presented.

Paper Details