COMPLEXITY RESULTS FOR SCHEDULING CHAINS ON A SINGLE MACHINE

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.


Issue Date:
1979
Publication Type:
Working or Discussion Paper
DOI and Other Identifiers:
Record Identifier:
https://ageconsearch.umn.edu/record/272176
Language:
English
Total Pages:
16
Series Statement:
REPORT 7907/0




 Record created 2018-04-25, last modified 2020-10-28

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)