|
|||||
|
|
| 运筹学与控制论两台平行机环境下加工时间退化的可拒绝排序问题 |
|
| 引用本文： | 王洪芳,罗成新, . 运筹学与控制论两台平行机环境下加工时间退化的可拒绝排序问题 [J]. 重庆师范大学学报(自然科学版), 2015, 0(6): 15 |
| 作者姓名： | 王洪芳 罗成新 |
| 作者单位： | 沈阳师范大学 数学与系统科学学院,沈阳 110034 |
| 摘 要： | 研究两台平行机环境下加工时间线性退化的可拒绝排序问题,工件的实际加工时间是关于该工件开始加工时间的线性函数,每个工件都有一个独立的截止工期,在截止工期之前或之后完工的任务将分别受到提前和误工工件惩罚。工件允许被拒绝,如果工件被拒绝则需要支付一定的拒绝费用。目标是分别确定接受工件和拒绝工件的任务集合,找到接受任务的最优排序和每个被接受工件的最优任务工期最小化工期、误工工件惩罚、总完工时间以及被拒绝工件的惩罚费用之和。证明了此 NP 难问题可以通过动态规划方法求得最优解,并通过动态规划运用简化执行空间的方法给出了复杂度为o(n5D2/ε2)的全多项式近似策略（FPTAS）,其中 n 表示工件的数量,ε 是允许误差界。 |
| 关 键 词： | 平行机 误工工件惩罚 工期 退化效应 全多项式近似策略 拒绝 |
Parallel-machine Scheduling Problem with Deteriorating Jobs and Rejection |
|
| WANG Hongfang,LUO Chengxin . Parallel-machine Scheduling Problem with Deteriorating Jobs and Rejection [J]. Journal of Chongqing Normal University:Natural Science Edition, 2015, 0(6): 15 |
|
| Authors: | WANG Hongfang LUO Chengxin |
| Abstract: | |
| Keywords: | |
| 点击此处可从《重庆师范大学学报(自然科学版)》浏览原始摘要信息 | |
| 点击此处可从《重庆师范大学学报(自然科学版)》下载全文 | |