Customer order scheduling to minimize the number of late jobs

Miao-Tsong Lin*, A. V. Kononov

*Corresponding author for this work

Research output: Contribution to journalArticle

22 Scopus citations

Abstract

In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date.

Original languageEnglish
Pages (from-to)944-948
Number of pages5
JournalEuropean Journal of Operational Research
Volume183
Issue number2
DOIs
StatePublished - 1 Dec 2007

Keywords

  • Approximability
  • Approximation algorithm
  • Multicover problem
  • Number of late jobs
  • Order scheduling

Fingerprint Dive into the research topics of 'Customer order scheduling to minimize the number of late jobs'. Together they form a unique fingerprint.

Cite this