| 退化工件误工数的双机自由作业排序问题 |
| |
| 引用本文： | 陈仁霞,李士生,冯琪,孟金涛.退化工件误工数的双机自由作业排序问题[J].佛山科学技术学院学报(自然科学版),2014(6):7-11. |
| |
| 作者姓名： | 陈仁霞 李士生 冯琪 孟金涛 |
| |
| 作者单位： | 1. 中原工学院 数学系,河南 郑州,450007
2. 郑州航空工业管理学院 数理系,河南 郑州,450015 |
| |
| 基金项目： | 国家自然科学基金数学天元基金项目(11326191)；国家自然科学基金项目(11401604，11401605)；河南省基础与前沿技术研究计划项目(132300410392)；河南省教育厅自然科学研究计划项目 |
| |
| 摘 要： | 探讨退化工件两台机器自由作业环境下的最小化加权误工工件的排序问题，其中所有工件具有相同的公共交货期。首先证明了最小化误工工件数问题是 NP 困难的；然后对最小化加权误工工件数问题给出了一个拟多项式时间算法；最后对几种特殊情形给出了多项式时间算法。
|
| 关 键 词： | 排序 自由作业 退化工件 NP- 困难性 |
Two-machine open shop scheduling with deteriorating job to the number of tardy jobs |
| |
| CHEN Ren-xia,LI Shi-sheng,FENG Qi,MENG Jin-tao.Two-machine open shop scheduling with deteriorating job to the number of tardy jobs[J].Journal of Foshan University(Natural Science Edition),2014(6):7-11. |
| |
| Authors: | CHEN Ren-xia LI Shi-sheng FENG Qi MENG Jin-tao |
| |
| Institution: | CHEN Ren-xia, LI Shi-sheng, FENG Qi, MENG Jin-tao, CHEN Ren-xia, LI Shi-sheng, FENG Qi, MENG Jin-tao (Department of Mathematics, Zhongyuan University of Technology, Zhengzhou 450007, China; 2. Department of Mathematics and Physics, Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou 450015,) |
| |
| Abstract: | This paper studies the problem of scheduling proportionally deteriorating jobs in two-machine open shop to minimize the number of tardy jobs, in which all jobs have the common due date. We first show that the unweighted problem is NP-hard, then we present a pseudo-polynomial-time algorithm for the weighed problem, and finally we develop polynomial algorithms to solve several special cases. |
| |
| Keywords: | scheduling open shop deteriorating jobs NP-hardness |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
