Scheduling jobs with agreeable processing times and due dates on a single batch processing machine

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

Abstract

In this paper we study the problems of scheduling jobs with agreeable processing times and due dates on a single batch processing machine to minimize total tardiness, and weighted number of tardy jobs. We prove that the problem of minimizing total tardiness is NP-hard even if the machine capacity is two jobs and we develop a pseudo-polynomial-time algorithm for an NP-hard special case of this problem. We also develop a pseudo-polynomial-time algorithm for the NP-hard problem of minimizing weighted number of tardy jobs, which suggests that this problem cannot be strongly NP-hard unless P=NP.
Original languageEnglish
Pages (from-to)159-169
Number of pages11
JournalTheoretical Computer Science
Volume374
Issue number1-3
DOIs
Publication statusPublished - 20 Apr 2007

Keywords

  • Agreeable
  • Batch processing
  • Scheduling

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this