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

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

硕｝：学位论文

ｓｈｏｐ型，因此，后面的内容主要围绕这两种类型的调度问题展开。其具有以下特点：①建模复杂性。②计算复杂性。③动态随机性。④多约束性。⑤多目标性。

处理机、任务或作业和目标函数三要素组成了调度问题。处理机的数量、类型和环境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的调度问题。为了描述方便，用Ｇｒａｈａｍ等人陋１首先使用的三元组来描述调度问题的种类，这样大大简化了调度问题的表示。三元组记号由三个域组成：ａＩｐｌｙ。它们具有下面的含义。

口域表示处理机的数量、类型和环境，它可以为：

１：单处理机。

‰：聊个同速机。

绒：脚个恒速机。

Ｊｉｃ。：删个变速机。

￡：朋个处理机，流水作业。

Ｄ矗：历个处理机，开放作业。

以：ｍ个处理机，异顺序作业。

腰：Ｊ类处理机，柔性流水作业。

ｐ域表示任务或作业的性质、加工要求和限制，资源的种类、数量和对加工的影响等约束条件。它同时可以包含多项，可能的项主要有：

，．；：任务有不同的到达时间。

％表示在弓和瓦之间的切换时间（ｓｅｔｕｐｔｉｍｅ）。

脚：加工时可中断。

胛ｃ，ｃ加ｆ船，ｉｎｔｒＰＰ，Ｄ甜舭Ｐ：表示任务的相关性，分别表示一般优先约束、链、入树和出树。

鸩：处理机资格限制。当处理机环境是平行机时，鸩可能出现在卢域中。当哆出现在卢域中时，不是所有的处理机都能加工任务乃，鸠表示能加工任务丁，的处理机集合。如果ｐ域中不出现Ｍ，，ｒ可以在任意处理机上加工。

６，．捌伽，ｌ：机器故障表示机器不能连续被使用。在确定性调度中，机器的不可用时间是固定的。对于同速机，可用的机器数在任何时刻都是时间的函数。

胛“：这个约束只能出现在流水作业中。当ｐ删甜出现时，作业按先进先出的原则进行：所有作业的每一道加工顺序性同。

６，Ｄ础：阻塞现象只能出现在流水作业中。如果在两个相邻的机器之间有一个容量有限的缓冲区，当缓冲区被占满时，上流的机器就不能释放加工完的作