File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard

TitleSingle machine scheduling to minimize total compression plus weighted flow cost is NP-hard
Authors
Wan, GYen, BPCLi, CL
KeywordsComputational complexity
Scheduling
Issue Date2001
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 2001, v. 79 n. 6, p. 273-280 How to Cite?
DOI: http://dx.doi.org/10.1016/S0020-0190(01)00143-0
AbstractThis article analyzes the computational complexity of a single machine scheduling problem to minimize total compression plus weighted flow cost. Vickson [Oper. Res. 28 (1980) 1155-1167] studied this problem and conjectured that it was NP-hard. The complexity of this problem remained open since then. We give a positive answer to this conjecture, showing that this problem is NP-hard. © 2001 Elsevier Science B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/85921
ISSN
0020-0190
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
ISI Accession Number ID
WOS:000170855100004
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorWan, Gen_HK
dc.contributor.authorYen, BPCen_HK
dc.contributor.authorLi, CLen_HK
dc.date.accessioned2010-09-06T09:10:46Z-
dc.date.available2010-09-06T09:10:46Z-
dc.date.issued2001en_HK
dc.identifier.citationInformation Processing Letters, 2001, v. 79 n. 6, p. 273-280en_HK
dc.identifier.issn0020-0190en_HK
dc.identifier.urihttp://hdl.handle.net/10722/85921-
dc.description.abstractThis article analyzes the computational complexity of a single machine scheduling problem to minimize total compression plus weighted flow cost. Vickson [Oper. Res. 28 (1980) 1155-1167] studied this problem and conjectured that it was NP-hard. The complexity of this problem remained open since then. We give a positive answer to this conjecture, showing that this problem is NP-hard. © 2001 Elsevier Science B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_HK
dc.relation.ispartofInformation Processing Lettersen_HK
dc.rightsInformation Processing Letters. Copyright © Elsevier BV.en_HK
dc.subjectComputational complexityen_HK
dc.subjectSchedulingen_HK
dc.titleSingle machine scheduling to minimize total compression plus weighted flow cost is NP-harden_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0020-0190&volume=79&issue=6&spage=273&epage=280&date=2001&atitle=Single+Machine+Scheduling+to+Minimize+Total+Compression+Plus+Weighted+Flow+Cost+is+NP-Harden_HK
dc.identifier.emailYen, BPC: benyen@hkucc.hku.hken_HK
dc.identifier.authorityYen, BPC=rp01121en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/S0020-0190(01)00143-0en_HK
dc.identifier.scopuseid_2-s2.0-0035975718en_HK
dc.identifier.hkuros67999en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0035975718&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume79en_HK
dc.identifier.issue6en_HK
dc.identifier.spage273en_HK
dc.identifier.epage280en_HK
dc.identifier.isiWOS:000170855100004-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridWan, G=7101629250en_HK
dc.identifier.scopusauthoridYen, BPC=7102564239en_HK
dc.identifier.scopusauthoridLi, CL=7501682598en_HK
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats