基于改进遗传算法的混合车间调度问题研究1(11)

基于改进遗传算法的混合车间调度问题研究

基于改进遗传算法的混合车问牛产调度问题研究

对组合的需要随问题的规模指数增长，以至求解大规模问题成为不可能…１。１９９８年，吴少岩，纪树新等在文献口２¨３３１中提出了不同的分支定界法，使得分支定界法成为求解许多调度问题很有希望的方法，因为它常常可为部分路径计算很强的下界，所以它成了求解大型组合问题为数不多的方法之一。基于运筹学方法的研究，这方面的详细论述我们可以参考文献∞制。值得注意的是，在用ＯＲ方法研究调度问题时，一般都是寻求调度特例的多项式时间的最优算法，近似算法或启发式算法。上面的分支定界法在下界精确的情况下是一种精确最优解。反之，当下界不十分精确时，它就是一种近似解。

二十世纪八十年代初，调度研究转向应用研究阶段∞副凹６Ｉ。以ＦｏｘＭＳ发表的文章为标志，开始了人工智能方法（ＡＩ）在ＪＳＳＰ调度问题中的研究应用¨７１。ＡＩ方法是通过提高调度方法的智能而解决各类生产调度问题方法的总称。它主要利用启发式规则来引导搜索并提供有效的搜索程序去寻找复杂问题的较优解，主要包括以下各方面的内容：一个是启发式搜索规则，研究的内容主要有宽度优先，深度优先，ｂｅａｍ搜，Ａ撑算法等。宽度优先，深度优先都是穷举搜索算法，从原理上讲，利用它们都能找到可行解，但却都不适合用于制造系统。因为可行解的空间非常庞大，超过了搜索时间与储存空间的限制。在ＡＩ中，较著名的搜索方法就是Ａ拌算法。它将分支定界法与动态规划法相结合，常用于图的路径搜索中。Ｎｉｌｓｓｏｎ证明了Ａ撑算法一定可以找到最优解¨８Ｉ。第二个是基于规则与基于知识的方法，单一的数学方法和工具不足以解决实际的调度问题，ＡＩ和专家系统的出现对解决调度问题的实时性和智能型提供了新的辅助手段。调度问题适合用ＡＩ和专家系统来解决是因为它本质上是启发式的，即需要用经验规则来获取可接受的解。它们用于调度可以克服数学规划与仿真方法的不足，能根据系统当前的状态和给定的优化目标，对知识库进行有效的启发式搜索和并行模糊推理，避开了繁琐的计算选择最优的调度策略，为在线决策提供支持。但也存在一定的不足，对新的调度环境适应性差，开发周期长，成本高，同时由于ＡＩ技术本身发展的限制，完全由计算机实现的系统大多是不良的。

在８０年代后期，ＹｕｅｈｗｅｒｎＹ等学者先后开展了基于调度系统处于不同的状态，采用不同的调度规则策略的动态调度方法的研究∞２Ｉ，其共同特点是：在支持某些活动发生的资源条件具备时砰为决策点），根据系统当时所处的属性状态，决定采取何种规则（策略），确定或选择活动发生的顺序和时间，即所谓的状态指导的智能调度方法。

另外，为克服数学表示和软件方法的局限性，１１９８８年，Ｄａｖｉｓ等ｎ６１提出基于数学规划的分解策略，将调度问题分解为多个子问题，分别考虑各子问题及其限制，提高了计算能力．数学分析模型通常用数学关系式表达所研究系统变量之间的相互关系。大多数分析模型是描述性的，即在一组条件下预测某一方案的各种结果数值。有一类预测模型需要分辨出最优结果，即需求出最优解，

在车间优化调度中，要从多个调度方案中寻求满足约束条件和目标的最佳