| 具有禁用区间的单机最小化加权完工时间和排序问题 |
| |
| 引用本文： | 吴志德,冯荣权.具有禁用区间的单机最小化加权完工时间和排序问题[J].数学的实践与认识,2010,40(6). |
| |
| 作者姓名： | 吴志德 冯荣权 |
| |
| 作者单位： | 1. 郑州大学数学系,河南郑州,450001
2. 北京大学数学科学院,北京,100871 |
| |
| 摘 要： | 研究具有禁用区间的单机最小化加权完工时间和排序问题.在该问题中,有一些禁用区间已经固定在机器上,工件将被安排在其余自由区间内进行加工且不能与禁用区间重叠.在文献中已经证明,该问题是强NP-困难的,并且在P不等于NP的假设下,该问题不存在2~(q(n))-近似算法.其中,n是工件个数,而q(n)是n的任一多项式.但是,其精确最优算法尚属未知.给出了该问题的一个动态规划最优算法.当禁用区间的数目是固定常数时,该算法是拟多项式的.
|
| 关 键 词： | 工序 单机 禁用区间 |
Single Machine Scheduling with Forbidden Intervals to Minimize Total Weighted Completion Time |
| |
| WU Zhi-de,FENG Rong-quan.Single Machine Scheduling with Forbidden Intervals to Minimize Total Weighted Completion Time[J].Mathematics in Practice and Theory,2010,40(6). |
| |
| Authors: | WU Zhi-de FENG Rong-quan |
| |
| Institution: | WU Zhi-de~1,FENG Rong-quan~2 (1.Department of Mathematics,Zhengzhou University,Zhengzhou 450001,China) (2.School of Mathematics Science,Peking University,Beijing 100871,China) |
| |
| Abstract: | We consider the single machine scheduling problem with forbidden intervals to minimize total weighted completion time.There are some forbidden intervals fixed on the machine.The jobs are free to be assigned to any free intervals on the machine in such a way that they do not overlap with the forbidden intervals.It have been showed in the literature that the problem is strongly NP-hard,and there is no 2~(q(n))-approximation algorithm if P≠NP,where n is the number of jobs and q(n) is any polynomial in n.However,no exact optimal algorithm was reported.In this paper,we present a dynamic programming algorithm to solve the problem.When the number of forbidden intervals is a fixed constant,our algorithm is of pseudo-polynomial. |
| |
| Keywords: | scheduling single machine forbidden intervals |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
