Indexed by:
Abstract:
We consider an assembling manufacture system where several suppliers provide component parts to a manufacturer, who assembles products from all the supplied component parts. The delivery time of any product is the maximum of the suppliers' delivery time of the parts needed for that product. We assume that the final stage is non-bottleneck. Chen and Hall (2007) show that the suppliers' problem of minimizing the total weighted number of tardy parts is binary (i.e., weakly) NP-hard and left open whether it is unary (i.e., strongly) NP-hard. In this paper we resolve this open problem by showing that it is unary NP-hard. Moreover we show that the suppliers' problem of minimizing the total late work of parts is also unary NP-hard. (C) 2013 Elsevier B.V. All rights reserved.
Keyword:
Reprint Author's Address:
Email:
Source :
INFORMATION PROCESSING LETTERS
ISSN: 0020-0190
Year: 2013
Issue: 17
Volume: 113
Page: 609-612
0 . 5 0 0
JCR@2022
ESI Discipline: COMPUTER SCIENCE;
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 10
SCOPUS Cited Count: 12
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2