文献类型：期刊文献

中文题名：链式先后关系下的单机分批排序问题

英文题名：One-machine Scheduling with Batching under Chain-like Precedence Constraints

作者：刘朝晖[1];俞文[1]

机构：[1]华东理工大学数学系,上海200237

年份：1999

卷号：3

期号：1

起止页码：65

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

收录：CSTPCD;;CSCD:【CSCD2011_2012】；

基金：国家自然科学基金

语种：中文

中文关键词：排序;链式先后关系;完工时间和;单机分批排序

外文关键词：scheduling, batching, chain-like precedence, total completion time, NP-hardness

摘要：在本文，我们证明链式先后关系下的单机分批排序问题是强NP困难的，解决了Albers和Brucker（1993）提出的待解决问题．关于此问题，Albers和Brucker（1993）也曾试图给出NP困难性证明，我们阐明了其证明中存在的缺陷．
In this paper, we show that one-machine scheduling problem with batching under chainlike precedence constraints is strongly NP-hard, which answers an open question proposedin Albers and Brucker (1993). In addition, we point out the error of Albers and Brucker(1993)'s proof on the ordinary NP-hardness of the poblem.