再上一篇:10.3  遗传算法
上一篇:10.4  习题
主页
下一篇:11.2  JSP 的遗传算法
再下一篇:11.3  仿真结果
文章列表

第 11 章  作 业 调 度

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

作业调度问题(JSP)是一个资源分配问题,只不过这里的资源被称作设备而已。这一

问题的求解目标是要找到一个将一组作业安排到设备上去以使作业可被“最优”完成的方

案。每个作业可由一些任务组成,而每个任务必须由特定的设备处理。一个调度是按先后

顺序条件将所有任务安排到设备上的一种方案。通常,约束的数目很大,使得JSP 成为一

个非常难解的组合问题( 完全问题)[99][57]。物流作业问题( )则是具有更严格条件

NP FSP

的 的特例,并可被约化为旅行商问题( )[137]。

JSP TSP

作业调度通常被称为n/m JSP,其中n是作业个数,m 是设备个数。图11.1是一个

5/3问题。图中每一个格是一个操作,每一横行是一个作业。每个操作都有三个下标i,j 和

k,其中i是作业序号,j 是操作序号,而k则是执行这一操作的设备的序号。每个格的长度

表示完成该操作所需的时间。

作业1 1,1,2 1,2,3 1,3,3 1,4,2 1,5,2 y

作业2 2,1,1 2,2,2 2,3,1 2,4,2 y

作业3 3,1,1 3,2,3 y

作业4 4,1,1 4,2,2 4,3,1 4,4,1 4,5,3 y

作业5 5,1,3 5,2,2 5,3,3 e

图 11.1  一个5/3作业调度问题

在寻找上述问题最优调度的过程中,调度是在满足先后关系约束的前提下,对这些格

子在每个设备上作出的安排。将有效的调度按照它们目标函数的相应得分排队,即可得到

得分最高的调度为最优调度。图11.2示出了在目标函数为最短完成时间情况下前述5/3

问题的最优调度。

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

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

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

图11.2  图11.1中5/3问题的最优调度

已经有许多用于求解作业调度问题的最优化方法被提出,包括神经元网络[180]和拉格

朗日松弛法[81][82]。不过,由于问题本身的难度很大,多数现有最优化算法都只适用于规模

较小的问题。另一方面,许多工业界依靠计算机模拟生成可行调度,而这样得到的可行调

度不一定保证好的性能。更进一步,评价调度算法的性能是一件很困难的事情,因为获取

#第109页-

规模很大且最优调度已知的测试问题本身就很困难。

遗传算法(GA)在作业调度问题上的应用,包括物流作业调度问题,是最近才发展起

来的研究方向(参见文献[31,43,49,88,103,112]),且研究的对象多为FSP 或较小规模

的JSP。

11.1  调度的分类

由于闲置时间可以无限多种方式插入任意给定调度,任意一个作业调度问题都可以

有无数个调度。不过,具有闲置时间的调度并不在我们的兴趣范围之内,因为它们通常

不能将目标函数最优化。在无限个数的调度中,特定的调度可视为主导调度。它们的定

义为

・ 半主动调度  在任意调度中将每个操作在不破坏操作顺序的条件下尽可能地向

左移,即可获得半主动调度。图11.3所示就是一个2/2问题的半主动调度(图中I 表示设

备空闲)。

设备1 2,1,1 I 1,2,1 I

设备2 1,1,2 I 1,3,2 p

调度1

设备1 2,1,1 I 1,2,1 I [

设备2 1,1,2 I 1,3,2

调度2

图11.3  调度2是从调度1得到的半主动调度

・ 主动调度  如果一个操作的左侧有一个足够放下它的空位,它可以跳过其它操作

而占据这一闲置时间。在一个半空调度中将每个操作在满足先后顺序约束的前提下尽可

能地向左跳,即可获得主动调度。图11.4中的主动调度(调度2)就是半主动调度(调度

1)中操作(2,1,2)跳过操作(1,2,2)所得。显然,最优调度一定是主动调度。

设备1 1,1,1 I I 2,2,1 F

设备2 I 1,2,2 2,1,2 I z

调度1

设备1 1,1,1 2,2,1 F

设备2 2,1,2 1,2,2 F

调度2

图11.4  调度2是从调度1得到的主动调度

・ 可安排操作  如果同一作业中排在一个操作前面的其它操作的总完成时间小于

或等于t,则称此操作在时间t 设备j 处可安排。如图11.1和11.2中的设备1,在操作

#第110页-

(4,1,1)之后,操作(3,1,1)和(2,1,1)均对设备1可安排。

・ 无延迟调度  在一个主动调度中,如果对每个闲置时间t 和每个设备j 都没有在

时间t 设备j 处的可安排操作,则称此调度为无延迟调度。简而言之,没有在处理它的设

备存在且闲置的情况下被延迟的作业。注意,无延迟调度是主动调度的一个子集,但是一

个最优调度并不一定是无延迟调度。以图11.5给出的2/2问题为例。调度1不是一个无

延迟调度,因为设备2在操作(2,1,2)可安排时处于闲置状态。相反,调度2则为一个无延

迟调度,且调度2比调度1先完成。

设备1 1,1,1 I 1,3,1

设备2 I 1,2,2 2,1,2 [

调度1

设备1 1,1,1 I 1,3,1

设备2 2,1,2 1,2,2 I

调度2

图11.5  延迟的和无延迟的调度

在这一章中,只考虑主动无延迟调度的生成,以找到具有最短完成时间的调度。