Open    Access



Some Discussions on Parallel Bounded Batch Scheduling to Minimize the Sum of Squared Machine Loads



Author(s)

Zengxia Cai, Xianzhao Zhang

Full-Text PDF XML     639 Views

DOI:10.17265/2159-5291/2016.02.002

College of Science, Linyi University, Linyi 276005, PR China.

We study the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) for this problem.