吴序一 产模式下车间调度的改进遗传算法 此类;不中断可切入类设备主要针对数控设备,在在停工时段起始时刻暂停、在停工时段结束时刻继 完成工件装夹并输入加工程序后即可自动进行加续,计划工时不包括停工时段;若设备为不中断可 工,即使操作工下班也不影响工作完成,说明加工切入类,则该工序忽略停工时段作用,继续加工直 过程可以切入停工时段继续加工,数控加工中心和到工序完成;⑧设备维护时段内不排入任何工序 HM电火花加工机等属此类.需要注意的是,当设 备安排有维护时段时,不中断可切入类设备上的工2应用遗传算法的实现 序不可切入维护时段 1.3制造系统描述 2.1编码 一个实际的非量产模式制造系统可描述为:其 编码是遗传算法的关键,本文采用一般字符串 制造系统,按主要工种分为W类机器,每类有h编码( gene ral string encod ings)和基于工序的编码 台,在时间段内要求加工N个制品产品),第;方法,将不同的制品按整数进行编码,利用这些编 制品含有S个工件,用M表示第制品的第正件,码表示不同的工序,且组成编码串来代表一个染色 完成该工件的加工需安排ω道工序,令O,表示制体,即一个可行的调度方案.编码前要按照工艺路 线指定制品内各工序的优先级,以及指定工序所作 品的顺序调度工序集合,OP=写为任务集用的制品、工件和操作的设备工种类型编码步骤 的总工序数,不同工件加工工艺路线和时间在调度是:①给不同制品指定整数编码基因,如0,1, 前已确定.调度的任务是安排所有制品加工工序,2,…等,基因数为n表示n个制品参加调度 且满足各种约束条件,使目标函数为 ②找到参加调度制品的最大工序数m,例如,参加 f(x)=m in(m ax/ Cnni) (1)调度的制品有4个,分别有6、6、5和8道工序 其中,m∈(1,2,.…W);n∈(1.2.…);x表示那么,m=8,③随机生成编码基因,组成编码长 个完整的可行调度;C表示第m类机器第n台的度为L=nⅫm的编码串,表示一个染色体,其中 完工时间 包含m个0~(n-1).例如,按照②例产生的两个 根据工厂实际,需要考虑如下约東:①工序可行调度个体基因编码为 只能在提供对应工种的机器上完成;②对于同 B=21103032122302310232031100012133, 工件,必须按照指定的工艺路径进行加工,只有完 P=22103013302123012110302002133123 成前工序的加工才能开始后一工序;③某一时刻 图1是染色体基因编码p的生成示例图.其 台机器只能进行一个工序的加工;④工件在加中,实基因座表示制品顺序调度工序集中的实际工 工过程中从一台机器转移到另一台机器的转移时间序基因所占用的实位置,虚基因座表示为染色体编 计入加工时间;⑤各工件的加工工艺路径和每道码而加入基因所占的虚位置.它们的区别主要体现 工序的加工时间己知,且不随排序改变;⑥若工在解码时实基因座基因会被还原为原工序进入调 件还有子层物料结构,则要求先完成所有子层工件度,而虚基因座基因将被忽略.在生成染色体编 的加工后才能进行该工件的加工;⑦当计划工序的过程中无需考虑实或虚基因座,只要保证生成的 遭遇计划停工时段时,若设备为中断类,则该工序编码符合包含m个0~(n-1),从而降低编码难度 制品0顺序调度T序集(基因0}包含61序 制品1噸序调度T序集(基因)包含6T序 染色体编码P1=2110 310002 制品2顺序调度工序集(基因2)包含5工序 制M3顺序调度τ序集(基因3}包含8T序 实基因座 虚基因座 图1遗传编码示例图 Fig. I Genetic encoding 201994-2009ChinaAcademicJournalElectronicPublishingHouseAllrightsreservedhup:/www.cnki.net© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 第 3期 吴序一 , 等 : 非量产模式下车间调度的改进遗传算法 273 此类 ; 不中断可切入类设备主要针对数控设备 , 在 完成工件装夹并输入加工程序后即可自动进行加 工 , 即使操作工下班也不影响工作完成 , 说明加工 过程可以切入停工时段继续加工 , 数控加工中心和 EDM电火花加工机等属此类. 需要注意的是 , 当设 备安排有维护时段时 , 不中断可切入类设备上的工 序不可切入维护时段. 113 制造系统描述 一个实际的非量产模式制造系统可描述为 : 其 制造系统 , 按主要工种分为 W 类机器 , 每类有 hw 台 , 在时间段 T内要求加工 N个制品 (产品 ) , 第 i 制品含有 Si个工件 , 用 M ij表示第 i制品的第 j工件 , 完成该工件的加工需安排 oij 道工序 , 令 Oi 表示制 品 i的顺序调度工序集合 , O P = ∑ N i =0 ∑ S i j =0 oij为任务集 的总工序数 , 不同工件加工工艺路线和时间在调度 前已确定. 调度的任务是安排所有制品加工工序 , 且满足各种约束条件 , 使目标函数为 f ( x) = m in (max{ Cm n } ). (1) 其中 , m ∈ (1, 2, …, W ) ; n ∈ (1, 2, …, hw ) ; x表示 一个完整的可行调度 ; Cm n表示第 m类机器第 n台的 完工时间. 根据工厂实际 , 需要考虑如下约束 : ①工序 只能在提供对应工种的机器上完成 ; ②对于同一 工件 , 必须按照指定的工艺路径进行加工 , 只有完 成前工序的加工才能开始后一工序 ; ③某一时刻 一台机器只能进行一个工序的加工 ; ④工件在加 工过程中从一台机器转移到另一台机器的转移时间 计入加工时间 ; ⑤各工件的加工工艺路径和每道 工序的加工时间已知 , 且不随排序改变 ; ⑥若工 件还有子层物料结构 , 则要求先完成所有子层工件 的加工后才能进行该工件的加工 ; ⑦当计划工序 遭遇计划停工时段时 , 若设备为中断类 , 则该工序 在停工时段起始时刻暂停、在停工时段结束时刻继 续 , 计划工时不包括停工时段 ; 若设备为不中断可 切入类 , 则该工序忽略停工时段作用 , 继续加工直 到工序完成 ; ⑧设备维护时段内不排入任何工序. 2 应用遗传算法的实现 211 编码 编码是遗传算法的关键 , 本文采用一般字符串 编码 ( general string encodings) 和基于工序的编码 方法 , 将不同的制品按整数进行编码 , 利用这些编 码表示不同的工序 , 且组成编码串来代表一个染色 体 , 即一个可行的调度方案. 编码前要按照工艺路 线指定制品内各工序的优先级 , 以及指定工序所作 用的制品、工件和操作的设备工种类型. 编码步骤 是 : ①给不同制品指定整数编码基因 , 如 0, 1, 2, …, 等 , 基因数为 n, 表示 n个制品参加调度 ; ②找到参加调度制品的最大工序数 m , 例如 , 参加 调度的制品有 4个 , 分别有 6、6、5和 8道工序 , 那么 , m = 8; ③随机生成编码基因 , 组成编码长 度为 L = n ×m 的编码串 , 表示一个染色体 , 其中 包含 m个 0 ～ ( n - 1). 例如 , 按照 ②例产生的两个 可行调度个体基因编码为 p1 = 21103032122302310232031100012133, p2 = 22103013302123012110302002133123. 图 1是染色体基因编码 p1 的生成示例图. 其 中 , 实基因座表示制品顺序调度工序集中的实际工 序基因所占用的实位置 , 虚基因座表示为染色体编 码而加入基因所占的虚位置. 它们的区别主要体现 在解码时实基因座基因会被还原为原工序进入调 度 , 而虚基因座基因将被忽略. 在生成染色体编码 的过程中无需考虑实或虚基因座 , 只要保证生成的 编码符合包含 m个 0～( n - 1) , 从而降低编码难度