倒数第四篇:10.4  习题
倒数第三篇: 第 11 章  作 业 调 度
主页
倒数第一篇:11.3  仿真结果
第一篇:《用 于 最 优 化 的 计 算 智 能》
文章列表

11.2  JSP 的遗传算法

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

应用GA 求解JSP 与用其求解MSP 类似。将GA应用于JSP 中的关键是采用有效的

编码方式以及适当的交叉、突变操作。在这一节中,我们介绍一些将n/m 作业调度问题转

换到m 排列的新的编码方式。在这一编码方式中,会用到PMX(部分匹配交叉),OX(有

序交叉)以及CX(循环交叉)等重新排序交叉操作(参见6.4节)。重新排序交叉操作适用

于排列问题,因为它们在交叉后所生成的符号串一定还是有效的。

11.2.1  JSP 的编码方式

排列可表示为整数符号串。可利用一类从旧的排列产生新的有效排序的交叉操作,即

重新排序交叉操作。这一技术已被成功地应用于求解那些可用排列表示的问题,诸如

TSP。利用GA求解JSP 的基本概念是扩展这一方法,将调度表示为一组排列,其中每个

排列对应于一个设备。重新排序操作被同时应用于所有排列并总是生成有效调度。

调度被表示为多个排列。在每个设备上都必须有特定数目的操作被执行。容量约束

要求在同一时刻这些操作只有一个被执行。因此,每个操作的排列表示了一个设备上的操

作处理序列,且所有设备上排列的组合表示一个可能的调度。

例如,图11.1给出了一个5/3 JSP 的约束条件。如果每个设备上的操作序列都可表

示如下:

#第111页-

设备1 2,1,1 2,3,1 3,1,1 4,1,1 4,3,1 4,4,1

a11 a12 a13 a14 a15 a16

设备2 1,1,2 1,4,2 1,5,2 2,2,2 2,4,2 4,2,2 5,2,2

a21 a22 a23 a24 a25 a26 a27

设备3 1,2,3 1,3,3 3,2,3 4,5,3 5,1,3 5,3,3

a31 a32 a33 a34 a35 a36

则排列

设备1 [a14,a13,a11,a15,a12,a16]

设备2 [a21,a26,a27,a24,a22,a25,a23]

设备3 [a35,a31,a32,a33,a36,a34]

可被用来表示图11.2所示调度。

显然,并非所有排列都可以代表有效调度。例如,在设备1上,排列[a14,a13,a12,a15,a11, a16]就不是一个有效调度, 因为a12所表示的操作(2,3,1)不能在 a11所表示的操作(2,1,1)之前进行。

11.2.2  调度的生成

对于多数实际目标函数来说,无延迟调度是一类非常重要的调度。生成无延迟调度也比生成任意的主动调度容易些。虽然无延迟调度不一定是最优的,但大量实验结果表明在多数情况下它们比其它主动调度要好。

可安排操作集是调度生成中的一个有用概念,并被简称为可安排子集。在任一时刻,可安排子集Sso是那些在其前面的操作已被排好的所有操作。对于一个n作业m 设备问题,Sso最初包括每个作业的第一个操作。一段时间之后,Sso的子集S 被选中并移入调度。这时,如果存在的话,紧随S 中每个操作之后的那些操作被加入Sso中。这一过程重复进行,直到Sso成为空集,调度完成。注意,当没有操作要在设备j 上执行时,设备j 闲置。设备j 的可安排子集可定义为分配给设备j 的操作中那些其前面的操作已被排好的操作集。利用可安排子集的概念,可以很容易地得到一个生成无延迟调度的程序。图11.6给出了调度程序的C语言伪编码。

调度

{

初始化;

while(not所有作业都已完成)

{

时间推进;

/* 检查每个设备的状态 * /

for(每个设备)

{

if(设备闲置或设备上当前操作已经完成)

将此设备标为可用;

}

#第112页-

/* 在可用设备上排入新的操作* /

for(每个设备)

{

if(这一设备已被标为可用)

{

计算这一设备的可安排子集; (

if(可安排子集非空)

{

根据预先定义的选取准则从可安排子集中选出一个新的操作;

将新选定的操作分配给该设备;

将该设备标为不可用;

}

}

}

}

}

图 11.6  生成主动无延迟调度的程序

多种选取准则可用来构成不同的调度程序。调度的质量取决于选取准则从每个设备

的可排子集中挑选操作的“智能”。下面列出了7个常用的选取准则[44]。它们被用于与GA

比较。

(1) RANDOM: 从每个设备的可安排子集中随机选取一个操作。

(2) MOPNR: 从每个设备的可安排子集中选取一个操作,且该操作属于具有最大数

目未完成操作的作业。

(3) MWKR-P: 从每个设备的可安排子集中选取一个操作,且该操作对应于一个可

安排操作之后的总处理时间最大的作业。

(4) MWKR/P: 从每个设备的可安排子集中选取一个操作,且该操作对应于一个未

安排操作的总处理时间与可安排操作本身的处理时间之比率最大的作业。

(5) SPT: 从每个设备的可安排子集中选取一个处理时间最小的操作。

(6) MWKR: 从每个设备的可安排子集中选取一个操作,且该操作对应于一个未安

排操作的总处理时间最大的作业。

(7) LWKR: 从每个设备的可安排子集中选取一个操作,且该操作对应于一个未安

排操作的总处理时间最小的作业。

正如上节所述,表示调度的排列用作决定哪一个操作应先处理的优先次序。例如,设

备1有一个排列[a14,a13,a11,a15,a12,a16],且此时设备1可用,并有可安排操作子集(a11,

a13,a12),则操作a13应选为下一个操作。

显而易见,排列与调度之间的映射关系不是唯一的,但这并不妨碍我们运用排列作为

GA 的编码方式。

#第113页-

11.2.3  遗传操作

本节讨论交叉和突变操作。突变操作相对简单一些,即随机选取一个设备及其排列中的两个元素,并交换这两个元素。不过,交叉操作就要稍微复杂一些。

因为一个n/m JSP 调度是由m 个排列表示的,对常用的PMX,OX和CX等重新排序操作(见6.4节)稍加改动即可加以使用。首先,重新排序操作必须作用于具有同样长度的排列。可是每个设备一般来说会有不同数目的操作。这使得交叉操作只能在同一设备的排列上使用。第二,这些重新排序操作的共同点在于它们对交叉截点的选择和对先后顺序的保护。因为设备并行运作,有必要使所有相关设备上的交叉截点相互关联。这可以通过在每个设备上选取起始和终止时间近乎相同的交叉截点来实现。这样,在这一时段上的先后顺序在交叉后仍可保持。

下面例子给出了上述交叉操作的示范。图11.1所示5/3JSP 的两个符号串被选来进行交叉。

符号串A

设备1 [a14,a13,a11,a15,a12,a16]

设备2 [a21,a26,a27,a24,a22,a25,a23]

设备3 [a35,a31,a32,a33,a36,a34]

符号串B

设备1 [a11,a14,a13,a15,a16,a12]

设备2 [a26,a27,a23,a24,a22,a25,a21]

设备3 [a35,a31,a33,a32,a34,a36]

假定对于符号串A 设备1的排列随机选择了位置2和4作为两个交叉截点,则处于位置2的操作a13的起始时间和处于位置4的操作a15的终止时间可从调度中发现。对于符号串A的设备2,两个相应的操作可据此找到,以使得第一个操作的起始时间非常接近于a13的起始时间,且第二个操作的终止时间非常接近于a15的终止时间。这两个操作将用作设备2的交叉截点。与此类似地,可找到设备3的交叉截点。若用符号“‖”来表示交叉截点,则有

符号串A

设备1 [a14,‖a13,a11,a15,‖a12,a16]

设备2 [‖a21,a26,a27,‖a24,a22,a25,a23]

设备3 [a35,a31,‖a32,a33,‖a36,a34]

在上面交叉截点中,设备1的操作a13与设备2的操作a21和设备3的操作a32具有基本相同的起始时间;设备1的操作a15与设备2的操作a27和设备3的操作a33具有基本相同的终止时间。在确定交叉截点之后,重新排序操作施用于每个设备的排列上并生成两个相对排列。例如,在上述交叉截点处施用OX之后,设备1和设备2的新的调度为

符号串A′

设备1 [a11,a14,a13,a15,a12,a16]

设备2 [a21,a26,a27,a24,a22,a25,a23]

#第114页-

设备3 [a35,a31,a32,a33,a36,a34]

符号串B′

设备1 [a14,a13,a11,a15,a16,a12]

设备2 [a21,a26,a27,a24,a22,a25,a23]

设备3 [a35,a31,a32,a33,a34,a36]