The unbounded parallel-batch scheduling with rejection

L. Q. Zhang, L. F. Lu, Chi To Ng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs; (4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them.
Original languageEnglish
Pages (from-to)293-298
Number of pages6
JournalJournal of the Operational Research Society
Volume63
Issue number3
DOIs
Publication statusPublished - 1 Mar 2012

Keywords

  • parallel-batch scheduling
  • polynomial-time algorithm
  • rejection penalty

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Management Information Systems
  • Marketing
  • Strategy and Management

Cite this