Operations Research Transactions ›› 2010, Vol. 14 ›› Issue (4): 11-20.

• Original Articles • Previous Articles     Next Articles

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

MIAO Cui-Xia, Zhang-Yu-Zhong, WANG Cheng-Fei   

  • Online:2010-12-15 Published:2010-12-15

Abstract: 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}\leq p_{ik}$ for all $i=1, \cdots, m $, $1\leq j\neq k\leq 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, \cdots, m $ and $j=1,\cdots, 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.