Bi-criteria scheduling on a single parallel-batch machine

作者：Fan, Baoqiang^*; Yuan, Jinjiang; Li, Shisheng

来源：Applied Mathematical Modelling, 2012, 36(3): 1338-1346.

DOI：10.1016/j.apm.2011.07.084

• Bi-criteria scheduling
• Complexity
• Pareto-optimal solution
• Fully polynomial-time approximation
• scheme

This paper considers bi-criteria scheduling on a single parallel-batch machine to minimizing two regular scheduling criteria that are non-decreasing in the job completion times. For minimizing the total weighted completion time and the makespan simultaneously, we prove that the problem is NP-hard in the ordinary sense and possesses a fully polynomial-time approximation scheme. For minimizing the weighted total number of tardy jobs and the makespan simultaneously, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme. Furthermore, we identify that all Pareto-optimal solutions for (Sigma(n)(j=1)w(j)C(j),C-max) and (Sigma(n)(j=1)w(j)C(j),C-max) can be found in pseudopolynomial time, respectively.

• 出版日期2012-3
• 单位鲁东大学; 郑州大学