将一类具有路径柔性的作业车间调度问题,分解为任务优化分配和任务优化调度两个子问题,结合遗传算法和启发式算法,提出了基于遗传算法的优化调度算法,并有实例证实了该算法的有效性。

维普资讯

第 8卷第 3期 2002年 3月

计算机集成制造系统

c Ms I

V 0.8】 No .3Ma r.2 0 0 2

Co pu e n e a e a f c urn Syse s m t rI t gr t d M nu a t ig tm

文章编号：0 6 6 1 (0 2 0 0 2 0 1 0 9 12 0 ) 3 2 9 4

基于遗传优化算法求解作业车间调度问题姜思杰，晓飞，全龙徐李(哈尔滨工业大学计算机科学与工程系，龙江黑暗尔滨 100) 5 0 1

摘要：一类具有路径柔性的作业车间调度问题，解为任务优化分配和任务优化调度两个子问题，台遗将分结传算法和启发式算法，出了基于遗传的优化调度算法，用实例证实了该算法的有数性。提并 关键词：作业车间；径柔性；发式算法；传算法路启遗中圈分类号： 2 2 T 3 8 0 F 7:P 9.7文献标识码： A

0引言具有路径柔性的作业车间 (o s o )度，于 J bh p调对充分发挥 J b h p灵活的特点是至关重要的。它 o so不仅可以避免 J b h p正常运行过程中的阻塞和拥 o so挤，且在系统出现异常状态 (故障 ),能维持而如时仍生产的继续进行。它虽给 J b h p调度系统带来了 o so

的解也不一定是最优解，至不是较优解。为此，甚本文提出一种新的基于遗传的优化调度算法，具有将路径柔性的 J b h p调度问题，解为任务优化分 o so分配和任务优化调度两个子问题，别利用文献E] 分 3中的基于遗传的最小平衡算法和本文的任务优化调度算法来求解，通过实例来验证该算法的有效性。并

很大的灵活性，也给 J b h p的优化调度问题带但 o so来了新的挑战。因为 J b h p的可行调度的数目比 oso传统相同规模的无路径柔性 J b h p的可行调度数 o so目大得多，这样太的可行解的范围内，找最优解在寻几乎不可能，只能求其近似最优调度解。 到目前为止，已有一些传统的启发式算法求解上述具有路径柔性的 J b h p优化调度问题一。 o so 在文献：] .用 P ti对具有路径柔性的

J b 1中先 er网 o so h p进行建模，后应用 II法搜索最优解。 l然算 J 1算法是人工智能中著名的搜索方法 A算法的一种改编算法，本质是分枝定界法和动态规划法的混其合运用。文献[]的作者采用遗传代码先确定各 2 J b类型的调度先后顺序，后用传统的人工智能 o然中的 F S(i ee em sac )索方法， B ftrd b a e rh搜 l对各个 J b的每一道工序按顺序进行调度，种 F S搜索 o这 B方法是宽度优先搜索法的一种改进方法。上述两种

1问题的描述考虑一具有路径柔性的 J b h p有 m台加工 o so,

设备 M ,,。现有一项含 t J b类型 .… M个 o J,J”,J共道工序的任务，这 m台加工设 在备上加工， J为 J b类型，的第 J道工序，这记… o .设个 J b类型的批量分别为 L S,,L 每 o S,L … S。一

一

个 J b类型由若干道有优先顺序的工序组成， o每道工序可以在一台或多台加工设备上加工，某称工序在某一台加工设备上的加工为一操作。因

一

此，一 J b类型的工件可以通过不同的操作序列某 o来完成，但工序上的先后顺序关系保持不变，这种不同的操作序列对 J b h p的柔性是至关重要的。本 o so文的重点优化目标是调度长度极小化。

下面，出本文所讨论的调度问题的约束条件：给 () 1一个操作一旦开始，就不能中断，除非加工设备发生故障；

方法都是基于人工智能中的搜索方法进行求解的， 其缺点是运行时间长，要很大的存储空间，索到需搜收稿日期： 0 1 4 2 0—0—0{订日期： 0 1 7 1。 2修 g 0—0— 2

( )每一台加工设备一次只能加工一个工件； 2 ( )不同 J b类型的工序之间没有优先权上的 3 o

基童项目：国家 8 3 C MS主题资助项目( 6—5 1 9 4 0 ) B/ 1 8 3 1— 4—0 1

作者简介：思杰 (9 o <鲜蘼 )黑龙江^,尔滨工业大学计算机科学与工程系博士后，姜 17一)男朝，哈主耍从事 U MS生产计划与控制等研究、E—mal in

￣ g o a .。【 i} g@ ax o c【;a I