Single machine parallel batch scheduling subject to precedence constraints

T.C.E. Cheng, C.T. Ng, J.J. Yuan and Z.H. Liu

Naval Research Logistics (NRL), 2004, vol. 51, issue 7, 949-958

Abstract: We consider the single machine parallel batch scheduling problems to minimize makespan and total completion time, respectively, under precedence relations. The complexities of these two problems are reported as open in the literature. In this paper, we settle these open questions by showing that both problems are strongly NP‐hard, even when the precedence relations are chains. When the processing times of jobs are directly agreeable or inversely agreeable with the precedence relations, there is an O(n2) time algorithm to minimize the makespan. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004

Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1002/nav.20035

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:wly:navres:v:51:y:2004:i:7:p:949-958

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().