最小化完成时间和加惩罚值和的批调度问题  

Batch Scheduling to Minimize the Sum of Total Completion Time Plus the Sum of Total Penalties

作　　者：李修倩[1] 冯好娣[1] 孙铮[2] 

机构地区：[1]山东大学计算机科学与技术学院,济南250101 [2]山东理工大学计算机科学与技术学院,山东淄博255049

出　　处：《计算机研究与发展》2013年第8期1700-1709,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60603007);山东省优秀中青年科学家奖励基金项目(BS2009DX009);山东大学自主创新基金项目(2012TS068)

摘　　要：考虑如下单机并行批调度问题:给定一些工件,每个工件有给定的处理时间以及惩罚值(可以拒绝处理某些工件,惩罚值为拒绝处理工件所付出的代价).给定一个可同时处理多个工件的批处理器.同时处理的工件形成一个批.同一批处理的工件具有相同的开始时间和结束时间,即开始时间加上这一批中所有工件的最大给定处理时间.判断如何选择要处理的工件,给这些工件分批以及给批排序使得目标函数值最小.对目标函数是被处理工件的完成时间之和加上被拒绝工件的惩罚值之和的情况,通过给出一个动态规划算法,证明当批容量为常量时问题是多项式时间可解的.Recently, quite a few works focus on single machine parallel batch scheduling problem with penalties. While most of them concern the makespan objective, little effort is put into the total completion time, which is studied in this paper. We study the following single machine parallel batch scheduling problem： There are n given jobs. Each job has a processing time and a rejection penalty （Some job may be rejected for processing. Some rejection penalty is paid if a job is rejected）. There is a single parallel batch machine that can process at most b jobs simultaneously. The jobs processed together form a batch. All jobs processed in the same batch have the same start time and the same completion time, that is, the start time plus the maximum processing time over all the jobs in the batch. We need to determine how to choose jobs for processing, divide these jobs into batches, and sequence these batches so that the sum of completion time of the processed jobs plus the sum of rejection penalties of the rejected ones is minimized. We give an O（（b2-b）× n26^2-2h＋2×b^b2-b-1）-time dynamic programming algorithm, and thus conclude that this problem can be solved in polynomial time when the batch size b is fixed.

关 键 词：批调度 拒绝 惩罚值 完成时间之和 动态规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]