谢　谢, 李晓丽, 孔祥玉

(1. 沈阳大学 装备制造综合自动化重点实验室, 辽宁 沈阳　110044;

2. 双辽市职业高级中学, 吉林 双辽　136400)



带有不可用区间、工件可拒绝的单机调度问题

谢谢1, 李晓丽2, 孔祥玉1

(1. 沈阳大学 装备制造综合自动化重点实验室, 辽宁 沈阳110044;

2. 双辽市职业高级中学, 吉林 双辽136400)

摘要:从企业生产经常发生的一些实际问题中提炼出一类带有不可用区间、工件可拒绝的单机调度问题.目标函数是最小化加工工件的总完工时间与拒绝工件的惩罚和.对于这个已证明为NP难的问题提出一个动态规划算法最优求解小规模问题,为求解大规模问题,改进了已有最坏性能为4的启发式算法,并进一步证明了该算法的最坏性能为(k为算法的迭代次数).

关键词:调度; 不可用区间; 拒绝工件; 动态规划; 启发式算法

对于大多数的经典调度模型,一些研究人员通常假设所有的工件必须接受加工,且加工机器不可以中断.然而在实际生产过程中,生产商为了获得更多的利润,往往会考虑拒绝一些加工时间较长且惩罚相对较小的工件加工.同时在生产企业加工过程中由于机器加工中断的现象频频发生,迫使机器在一段时间内不能加工任何工件,为了减少机器停产给企业带来的损失,带有不可用区间的调度问题也引起了管理者的关注.因此,本文同时考虑带有不可用区间、工件加工可拒绝的单机调度问题,目标函数是最小化加工工件的总完工时间与……