| 带有不可用区间的单机排序问题 |
| |
| 引用本文： | 刘澈,罗成新.带有不可用区间的单机排序问题[J].沈阳师范大学学报(自然科学版),2013,31(3):353-355. |
| |
| 作者姓名： | 刘澈 罗成新 |
| |
| 作者单位： | 沈阳师范大学数学与系统科学学院,沈阳,110034 |
| |
| 基金项目： | 国家自然科学基金资助项目 |
| |
| 摘 要： | 考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。一个工件或者被拒绝加工,或者被接受。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。在张丽琦工作的基础上增加了一个不可用区间,机器在此区间内不能加工工件,并且在同一时刻至多加工一个工件。目标函数是最小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出一个动态规划算法,然后通过构造输入,将拒绝惩罚进行取整运算,再通过动态规划算法,得到拒绝惩罚取整后的一个最优排序,按照这个工件排序得到原问题的一个可行排序,最后借助一个3—因子算法得到一个全多项式时间近似方案。
|
| 关 键 词： | 到达时间 拒绝工件 不可用区间 时间表长 |
Single machine scheduling problem with unavailable interval |
| |
| LIU Che
,
LUO Chengxin.Single machine scheduling problem with unavailable interval[J].Journal of Shenyang Normal University: Nat Sci Ed,2013,31(3):353-355. |
| |
| Authors: | LIU Che LUO Chengxin |
| |
| Institution: | (School of Mathematics and System Science,Shenyang Normal University,Shenyang 110034,China) |
| |
| Abstract: | |
| |
| Keywords: | release dates rejection unavailable interval makespan |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
