Bounded single-machine parallel-batch scheduling with release dates and rejection

Lingfa Lu, Edwin Tai Chiu Cheng, Jinjiang Yuan, Liqi Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

56 Citations (Scopus)


We consider the bounded single-machine parallel-batch scheduling problem with release dates and rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and then processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs. When the jobs have identical release dates, we present a polynomial-time algorithm. When the jobs have a constant number of release dates, we give a pseudo-polynomial-time algorithm. For the general problem, we provide a 2-approximation algorithm and a polynomial-time approximation scheme.
Original languageEnglish
Pages (from-to)2748-2751
Number of pages4
JournalComputers and Operations Research
Issue number10
Publication statusPublished - 1 Oct 2009


  • Parallel-batch
  • Polynomial-time approximation scheme
  • Rejection penalty
  • Scheduling

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Bounded single-machine parallel-batch scheduling with release dates and rejection'. Together they form a unique fingerprint.

Cite this