极小化最大完工时间及拒绝费用的单机可拒绝分批排序  

Single Machine Batch Scheduling with Rejection to Minimize Makespan

作　　者：王珍[1] 曹志刚[2] 张玉忠[1] 

机构地区：[1]曲阜师范大学运筹与管理学院,日照市276826 [2]山东外国语职业学院基础部,山东省济南市250100

出　　处：《曲阜师范大学学报（自然科学版）》2007年第2期35-38,共4页Journal of Qufu Normal University(Natural Science)

基　　金：山东省自然科学基金资助(Y2005A04)

摘　　要：首次考虑了工件可拒绝的单机分批排序问题,目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和.对于工件同时到达的情况,本文通过动态规划算法给出了多项式时间的精确算法,借助于数据结构中的堆排序,我们将算法复杂性降低为O(n2logB).In this paper, a variant single machine scheduling problem with both batching and rejection is addressed. The objective to minimize the makespan of the accepted jobs plus the summation of the rejected ones. A dynamic programming algorithm with time complexity O（n^2 log B） is presented, where B is the batch size.

关 键 词：排序 分批 可拒绝 最大完工时间 动态规划 

分 类 号：O223[理学—运筹学与控制论]