Improved Algorithms for Single-Machine Serial-Batch Scheduling with Rejection to Minimize Total Completion Time and Total Rejection Cost

Yunqiang Yin, Edwin Tai Chiu Cheng, Dujuan Wang, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

20 Citations (Scopus)


Recently, Shabtay considered a scheduling problem on a single serial-batching machine with rejection to minimize the dual criteria of total completion time and total rejection cost, where the number of jobs to be included in each batch is not restricted. He studied four variants of the problem: the first is to minimize the sum of the two criteria; the second and third are to minimize one criterion, subject to the other criterion not exceeding a given value; and the last is to find the Pareto-optimal solutions for the bicriterion problem. Shabtay provided an O(n5) algorithm for the first variant and an O(n6/ϵ2) fully polynomial-time approximation scheme (FPTAS) for the fourth variant. In this paper, we provide an alternative O(n4) algorithm to solve the first variant and an O(n5/ϵ) FPTAS for the fourth variant, which are more efficient than those developed by Shabtay from a theoretical perspective. However, when the size of each batch is bounded by a given number b > 1, the corresponding time complexities of our algorithms for the first and fourth variants reduce to O(bn3) and O(bn4/ϵ), respectively.
Original languageEnglish
Article number7364271
Pages (from-to)1578-1588
Number of pages11
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Issue number11
Publication statusPublished - 1 Nov 2016


  • Batch scheduling
  • bicriterion scheduling
  • dynamic programming
  • rejection
  • total completion time

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this