On the complexity of bi-criteria scheduling on a single batch processing machine

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)629-638
Number of pages10
JournalJournal of Scheduling
Volume13
Issue number6
DOIs
Publication statusPublished - 1 Dec 2010

Keywords

  • Batch processing
  • Bi-criteria
  • Complexity
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Engineering(all)
  • Management Science and Operations Research

Cite this