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

作　　者：Zengxia Cai Xianzhao Zhang 

机构地区：[1]College of Science, Linyi University, Linyi 276005, PR China.

出　　处：《Journal of Mathematics and System Science》2016年第2期60-65,共6页数学和系统科学（英文版）

摘　　要：We sttidy 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.

关 键 词：SCHEDULING Parallel batch Polynomial time approximation scheme FPTAS 

分 类 号：O156.1[理学—数学] TH165[理学—基础数学]