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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Scheduling Fully Parallel Jobs with Integer Units

  • Junyi Zhang,
  • Juan Zou,
  • Mingyu Ma

摘要

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.