Complexity of single machine scheduling subject to nonnegative inventory constraints

Dirk Briskorn, Byung Cheon Choi, Kangbok Lee, Joseph Leung, Michael Pinedo

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

This paper focuses on single machine scheduling subject to inventory constraints. Jobs either add items to an inventory or remove items from that inventory. Jobs that have to remove items cannot be processed if the required number of items is not available. We consider scheduling problems on a single machine with the minimization of the total weighted completion time, the maximum lateness, and the number of tardy jobs, respectively, as objective and determine their computational complexity. Since the general versions of our problems turn out to be strongly NP-hard, we consider special cases by assuming that different jobs have certain parameter values in common. We determine the computational complexity for all special cases when the objective is either to minimize total completion time or to minimize maximum lateness and for several special cases when the objective is either to minimize total weighted completion time or to minimize the number of tardy jobs.

Original languageEnglish (US)
Pages (from-to)605-619
Number of pages15
JournalEuropean Journal of Operational Research
Volume207
Issue number2
DOIs
StatePublished - Dec 1 2010

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Computational complexity
  • Inventory constraints
  • Machine scheduling
  • Polynomial-time algorithms
  • Strong NP-hardness

Fingerprint Dive into the research topics of 'Complexity of single machine scheduling subject to nonnegative inventory constraints'. Together they form a unique fingerprint.

Cite this