|
|||||
|
|
| 带到达时间、不可用区间、拒绝工件的单机排序问题 (三峡地区资源环境生态研究) |
|
| 引用本文： | 刘澈,罗成新 .带到达时间、不可用区间、拒绝工件的单机排序问题 (三峡地区资源环境生态研究) [J].重庆师范大学学报(自然科学版),2013,30(1):17-20. |
| 作者姓名： | 刘澈 罗成新 |
| 作者单位： | 沈阳师范大学数学与系统科学学院,沈阳,110034 |
| 摘 要： | 考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个工件。本文的目标函数是极小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出了一个近似算法,并通过引理1证明出此算法是3-因子算法;其次提出了一个动态规划算法,然后通过修改这个动态规划算法的执行过程来减少运行时间,进而得到了一个全多项式时间近似方案,证明出该方案的时间复杂性为O(n2/ε) |
| 关 键 词： | 到达时间 拒绝工件 不可用区间 时间表长 |
Single Machine Scheduling Problem with Release Dates, Rejection and an Unavailable Interval |
|
| LIU Che,LUO Cheng-xin .Single Machine Scheduling Problem with Release Dates, Rejection and an Unavailable Interval[J].Journal of Chongqing Normal University:Natural Science Edition,2013,30(1):17-20. |
|
| Authors: | LIU Che LUO Cheng-xin |
| Institution: | (College of Mathematics and System Science,Shenyang Normal University,Shenyang 110034,China) |
| Abstract: | |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《重庆师范大学学报(自然科学版)》浏览原始摘要信息 | |
| 点击此处可从《重庆师范大学学报(自然科学版)》下载免费的PDF全文 | |