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

51 Citations (Scopus)

Abstract

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
Volume36
Issue number10
DOIs
Publication statusPublished - 1 Oct 2009

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this