| 链式先后关系下的单机分批排序问题 |
| |
| 引用本文： | 刘朝晖 俞文Ci.链式先后关系下的单机分批排序问题[J].运筹学学报,1999,3(1):65-68. |
| |
| 作者姓名： | 刘朝晖 俞文Ci |
| |
| 作者单位： | 华东理工大学数学系!上海，200237 |
| |
| 摘 要： | 在本文，我们证明链式先后关系下的单机分批排序问题是强NP困难的，解决了Albers和Brucker（1993）提出的待解决问题．关于此问题，Albers和Brucker（1993）也曾试图给出NP困难性证明，我们阐明了其证明中存在的缺陷．
|
| 关 键 词： | 排序 分批 链式先后关系 完工时间和 NP困难性 |
One-machine Scheduling with Batching under Chain-like Precedence Constraints |
| |
| ZHAOHUI LIU,WENCI YU.One-machine Scheduling with Batching under Chain-like Precedence Constraints[J].OR Transactions,1999,3(1):65-68. |
| |
| Authors: | ZHAOHUI LIU WENCI YU |
| |
| Abstract: | 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. |
| |
| Keywords: | scheduling batching chain-like precedence total completion time NP-hardness |
| 本文献已被 CNKI 维普 等数据库收录！ |
