COMPLEXITY RESULTS FOR SCHEDULING CHAINS ON A SINGLE MACHINE

J. K. Lenstra and A. H. G. Rinnooy Kan

No 272176, Econometric Institute Archives from Erasmus University Rotterdam

Abstract: We investigate the computational complexity of deterministic sequencing problems in which unit-time jobs have to be ;.cheduled on a single machine subject to chain-like precedence constraints. NP-hardness is established for the cases in which the number of late jobs or the total weighted tardiness is to be minimized, and for several related problems involving the total weighted completion time criterion.

Keywords: Agricultural and Food Policy; Research Methods/Statistical Methods (search for similar items in EconPapers)
Pages: 16
Date: 1979
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ageconsearch.umn.edu/record/272176/files/erasmus112.pdf (application/pdf)
https://ageconsearch.umn.edu/record/272176/files/erasmus112.pdf?subformat=pdfa (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ags:eureia:272176

DOI: 10.22004/ag.econ.272176

Access Statistics for this paper

More papers in Econometric Institute Archives from Erasmus University Rotterdam Contact information at EDIRC.
Bibliographic data for series maintained by AgEcon Search ().