Scheduling Fully Parallel Jobs with Integer Units
摘要
We consider m identical machines scheduling problems with fully parallel jobs. Each job \(J_j\) requires processing time \(p_j\) and can be executed on any machine at any time unit. In this paper, four scheduling problems are considered: (1) minimize the maximum cost, (2) minimize the total completion time, (3) minimize the weighted number of tardy jobs, and (4) minimize the total weighted tardiness. For the first two problems, we develop optimal polynomial-time algorithms to solve them, respectively. For the third problem, we design a polynomial-time algorithm if all weights are equal to one; we propose a pseudo-polynomial-time algorithm for the general case. For the last problem, we design polynomial-time algorithms for solving some special cases of this problem, respectively.