两个带有分批费用的单机平行分批排序问题

Two problems about single machine parallel batching with batching costs

假定工件和批处理机都在零时刻到达,工件被成批进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用。第1个问题对目标函数为任意的正则函数与分批费用之和的情形,利用动态规划方法给出了拟多项式时间算法;第2个问题对目标函数为误工工件数与分批费用之和的极小化问题,同样利用动态规划方法给出了O(n4)的算法。

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.Furthermore,we assume that there is a batching cost for each batch.We give a pseudo-polynomial time algorithm for the first problem of minimizing the sum of the arbitrary regular function and batching costs.The second problem is the problem of minimizing the sum of the number of late jobs and batching costs,and we solve it by using an algorithm.