\input zb-basic
\input zb-ioport
\iteman{io-port 06058805}
\itemau{Fan, Baoqiang; Yuan, Jinjiang; Li, Shisheng}
\itemti{Bi-criteria scheduling on a single parallel-batch machine.}
\itemso{Appl. Math. Modelling 36, No. 3, 1338-1346 (2012).}
\itemab
Summary: 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 $(\sum_{j=1}^nw_jC_j,C_{\max})$ and $(\sum_{j=1}^nw_jU_j,C_{\max})$ can be found in pseudo-polynomial time, respectively.
\itemrv{~}
\itemcc{}
\itemut{bi-criteria scheduling; complexity; Pareto-optimal solution; fully polynomial-time approximation scheme}
\itemli{doi:10.1016/j.apm.2011.07.084}
\end