无关机上极小化求和问题的平行分批排序(英文)

Parallel-batch Scheduling on Unrelated Machines to Minimize the Sum Objectives

本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了p_(ij)=p_i(i=1,…,m;j=1,…,n)这种情况,当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.

In this paper,we consider the parallel-batch scheduling problems on unrelated parallel machines.For the unbounded parallel-batch model,we discuss the special case：the processing times are agreeable,i.e.,p_（ij）≤p_（ik） for all i = l,…,m, 1≤j≠k≤n,where m and n is the number of machines and jobs,respectively,and we design a dynamic programming algorithm to minimize the total completion time in polynomal time when m is constant.For the bounded parallel-batch model,we discuss the case with p_（ij） = p_i for i = 1,…,m and j = 1,…,n,give an optimal algorithm for the general schedule to minimize the total weighted completion time,and design a pseudo-polynomial time algorithm for the case with rejection to minimize the sum of the total weighted completion time of the accepted jobs and the total penalty of the rejected jobs.