Operations Research Transactions ›› 2010, Vol. 14 ›› Issue (4): 11-20.
• Original Articles • Previous Articles Next Articles
MIAO Cui-Xia, Zhang-Yu-Zhong, WANG Cheng-Fei
Online:
Published:
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.
MIAO Cui-Xia, Zhang-Yu-Zhong, WANG Cheng-Fei. Parallel-batch Scheduling on Unrelated Machines to Minimize the Sum Objectives[J]. Operations Research Transactions, 2010, 14(4): 11-20.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.ort.shu.edu.cn/EN/
https://www.ort.shu.edu.cn/EN/Y2010/V14/I4/11