| 带有退化工件和机器维修区间的单机排序问题 |
| |
| 引用本文： | 张敏娇,罗成新.带有退化工件和机器维修区间的单机排序问题[J].沈阳师范大学学报(自然科学版),2013,31(3):348-352. |
| |
| 作者姓名： | 张敏娇 罗成新 |
| |
| 作者单位： | 沈阳师范大学数学与系统科学学院,沈阳,110034 |
| |
| 基金项目： | 国家自然科学基金资助项目 |
| |
| 摘 要： | 考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚;如果被加工,那么工件被排在机器上(机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件)进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP-难的。
|
| 关 键 词： | 拒绝工件 退化 全多项式近似方案 维修区间 排序 |
Single-machine scheduling problem with deteriorating jobs and fixed machine non-availability interval |
| |
| ZHANG Minjiao
,
LUO Chengxin.Single-machine scheduling problem with deteriorating jobs and fixed machine non-availability interval[J].Journal of Shenyang Normal University: Nat Sci Ed,2013,31(3):348-352. |
| |
| Authors: | ZHANG Minjiao LUO Chengxin |
| |
| Institution: | (School of Mathematics and System Science,Shenyang Normal University,Shenyang 110034,China) |
| |
| Abstract: | |
| |
| Keywords: | rejection job deteriorating fully polynomial time approximation scheme non-availability interval scheduling |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
