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

Single Machine Batch Scheduling with Rejection to Minimize Makespan

首次考虑了工件可拒绝的单机分批排序问题,目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和.对于工件同时到达的情况,本文通过动态规划算法给出了多项式时间的精确算法,借助于数据结构中的堆排序,我们将算法复杂性降低为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.