一种解决抢占式作业车间调度问题的基于约束控制规则的启发式算法[外文翻译].doc

一种解决抢占式作业车间调度问题的基于约束控制规则的启发式算法

CLAUDE LE PAPE
Bouygues, Direction des Technologies Nouvelles, 1, av. E. Freyssinet, F-78061 Saint-Quentin-en-Yvelines
电子邮箱：clp@challenger.bouygues.fr
摘要
近几年来，约束规划已经被广泛运用于解决各种学科以及工业非抢占式调度问题，举例来说：优先问题即：活动不能被中断的问题。相比而言，运筹学和人工智能领域几乎都没有注意到抢占式调度问题。由于一些特殊应用需求的激发，我们从事一个关于解决抢占式调度问题的约束规划技术适应性的研究。本文将介绍那些我们推广的算法和那些我们得到的关于抢占式的各种有名的“作业车间调度问题”的研究结果。相比较文献中使用的两种众所周知的连续作业车间调度实例，十种启发式研究战略结合两种不同约束传播技术都表明：最好的结合基于“极限差异研究”和“边界发现”技术，已经显示出能为优化车间调度问题提供很好的解决方案。以10项作业和10台机器（100个活动）为例，一个离最优化解决方案相对距离0.32%的平均值可以在5分钟内达到。

关键字：抢占式调度 作业车间调度 约束规划 约束传播 资源约束 时间表 临界发现 极限差异研究

1．绪论
广泛的说，约束规划可以被定义为基于以下3种规则的规划方法：
 在一个基于约束的规划中，待解决问题已经以参数和参数约束的形式被明确的表示出来，分离出来。这个分离保证待解决（问题）被清晰定义。在很多案例中,当相应的有待的解决问题发生变化时，它被简化为一个约束规划应用的修订或者扩展，举例来说，一个制造车间的新机器取代旧机器可能导致新的约束的引入和旧的约束的移出；但是，在一些案例中，同样的解决问题的算法将继续应用，以一个不同问题的定义作为输入。
 给定一个待解决的基于约束定义的问题和一系列结果，将它们转化为约束：一个表示“约束传播”的纯粹动推论过程已经被用来传播约束推论。每次当一个新的