51. Bi-criteria scheduling on a single parallel-batch machine
- Author
-
Fan, Baoqiang, Yuan, Jinjiang, and Li, Shisheng
- Subjects
- *
SCHEDULING , *PARALLELS (Geometry) , *MAXIMA & minima , *APPROXIMATION theory , *POLYNOMIALS , *ALGORITHMS , *NUMERICAL analysis - Abstract
Abstract: 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 and can be found in pseudo-polynomial time, respectively. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF