| Article ID: | iaor20108143 |
| Volume: | 13 |
| Issue: | 6 |
| Start Page Number: | 629 |
| End Page Number: | 638 |
| Publication Date: | Dec 2010 |
| Journal: | Journal of Scheduling |
| Authors: | Liu L, Ng T, Cheng E |
| Keywords: | programming: multiple criteria |
This paper considers hierarchical bi-criteria scheduling on a single batch processing machine where the primary criterion is the makespan. We show that the problem where the secondary criterion is the total completion time can be solved in polynomial time for a given machine capacity and the problem where the secondary criterion is the (weighted) number of late jobs is (strongly) NP-hard.