带有分批费用的容量有界的单机平行分批排序问题

考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b²m2m²222^m).

The Problem of Bounded Batch Capacity with Batching Costs About Parallel Batching

The article is about how to minimizing the sum of the total completion time and batching costs about the single machine parallel batching problem considering adding salary costs or packaging costs to the batching costs.First we assume that the jobs and the machine are available from time zero onwards.The jobs that are processed together form a batch and once processed the job can't be interrupted.The processing time of a batch is equal to the maximum processing time of any job assigned to it.Moreover,we assume that there is a batching cost for each batch.Then if it is supposed that there are m different processing times and the batch capacity is bounded as a fixed value of 6.For the problem of minimizing the sum of ∑ C_j and batching costs,the article gives a polynomial time algorithm using dynamic programming method,and the time limit is O(b~2m~22m).