Approximation Algorithm of Minimizing Makespan in Parallel Bounded Batch Scheduling

摘要：

We consider the problem of minimizing the makespan(Cmax) on m identical parallel batch processing machines. The batch processing machine can process up to B jobs simultaneously.The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. For a batch of jobs, the processing time of the batch is equal to the largest processing time among the jobs in the batch. In this paper, we design a fully polynomial time approximation scheme (FPTAS) to solve the bounded identical parallel batch scheduling problem Pm|B ＜ n|Cmax when the number of identical parallel batch processing machines m is constant.

关键词： Approximation algorithm Bounded batch scheduling Makespan FPTAS Dynamic programming

作者: Jianfeng Ren Yuzhong Zhang Sun Guo

作者单位: College of Operations Research and Management Sciences, Qufu Normal University, Shangdong, 276826, C Department of Mathematics, Qufu Normal University, Shangdong, 276826, China

会议类型: 国际会议

会议名称: The Seventh International Symposium(ISORA08)(第七届国际效力研究及其应用学术会议)

会议地点: 云南丽江

会议语种:英文

页码: 53-59

在线出版日期: 2008-10-31（万方平台首次上网日期，不代表论文的发表时间）