两台平行机环境下加工时间退化的可拒绝排序问题

摘要：

研究两台平行机环境下加工时间线性退化的可拒绝排序问题,工件的实际加工时间是关于该工件开始加工时间的线性函数,每个工件都有一个独立的截止工期,在截止工期之前或之后完工的任务将分别受到提前和误工工件惩罚.工件允许被拒绝,如果工件被拒绝则需要支付一定的拒绝费用.目标是分别确定接受工件和拒绝工件的任务集合,找到接受任务的最优排序和每个被接受工件的最优任务工期最小化工期、误工工件惩罚、总完工时间以及被拒绝工件的惩罚费用之和.证明了此NP难问题可以通过动态规划方法求得最优解,并通过动态规划运用简化执行空间的方法给出了复杂度为O(n5 D2/ε2)的全多项式近似策略(FPTAS),其中n表示工件的数量,ε是允许误差界.

关键词：平行机、误工工件惩罚、工期、退化效应、全多项式近似策略、拒绝

所属期刊栏目：32

分类号：O223(运筹学)

资助基金：国家自然科学基金No.11171050

在线出版日期：2015-11-27（万方平台首次上网日期，不代表论文的发表时间）

页码：15-19