| 单机交错排序问题的复杂性证明 |
| |
| 引用本文： | 于彬,王广彬,赵立宽,孙亮.单机交错排序问题的复杂性证明[J].高师理科学刊,2007,27(4):4-7. |
| |
| 作者姓名： | 于彬 王广彬 赵立宽 孙亮 |
| |
| 作者单位： | 1. 青岛科技大学,数理学院,山东,青岛,266061
2. 青岛崂山一中,山东,青岛,266071 |
| |
| 摘 要： | 关于共同宽容交货的单机排序问题,对于宽容区间大小给定,位置不固定的情况,给出了5条性质,证明该问题是NP-困难的.
|
| 关 键 词： | 宽容区间 超前迟后 NP-困难 |
| 文章编号： | 1007-9831（2007）04-0004-04 |
| 收稿时间： | 2007-03-10 |
| 修稿时间： | 2007年3月10日 |
The proof of complexity about an interlacing form single-machine scheduling problem |
| |
| YU Bin,WANG Guang-bin,ZHAO Li-kuan,SUN Liang.The proof of complexity about an interlacing form single-machine scheduling problem[J].Journal of Science of Teachers＇College and University,2007,27(4):4-7. |
| |
| Authors: | YU Bin WANG Guang-bin ZHAO Li-kuan SUN Liang |
| |
| Institution: | 1. School of Mathematics and Physics, Qingdao University of Science and Technology, Qingdao 266061, China; 2. Laoshan No.1 Middle School of Qingdao, Qingdao 266071, China |
| |
| Abstract: | Consided the single machine schedeling problem with a common due window.Corresponding to the following cases that the width of the due window is given and the site of the due window is free,listed five properties about it and proved it is NP-hard. |
| |
| Keywords: | common due window earliness-tardiness NP-hard |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
