A Simplified Enumeration Scheme for Minimizing Total Completion Time plus Total Penalty with Release Dates

摘要：

　　In this paper, we consider the problem of scheduling jobs with release dates and rejection on a bounded single parallel batching machine.Our objective is to minimize the sum of total completion time of the accepted jobs and the total penalty of the rejected jobs.We need to determine how to choose jobs for processing, divide these jobs into batches, and sequence these batches so that the objective function is minimized.We give a simplified enumeration approximation scheme for this problem by applying combinatorial optimization techniques with delicate analysis.

关键词： Batch scheduling PTAS Release date Total penalty

作者: Yong Zhang Haodi Feng Zheng Sun

作者单位: School of Computer Science and Technology,Shandong University,Jinan 250101,China School of Computer Science and Technology,Shandong University of Technology,Zibo 255049,China

会议类型: 国内会议

会议名称: 2015全国理论计算机科学学术年会

会议地点: 金华

会议语种:英文

页码: 1-10

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