《基于遗传算法的服装工序编排规划_楼亚芳.docx》由会员分享，可在线阅读，更多相关《基于遗传算法的服装工序编排规划_楼亚芳.docx（4页珍藏版）》请在三一文库上搜索。
1、第 14 卷第4 期中原工学院学报Vol. 14 No. 42003 年 12 月JOURNAL OF ZHONGYUAN INSTITUTE OF TECHNOLOGYDec. , 2003文章编号: 1671- 6906( 2003) 04- 0050- 03基于遗传算法的服装工序编排规划楼亚芳( 东华大学, 上海 200051)摘 要: 本文讨论了建立服装工序编排系统的必要性, 在进行服装工序拆分、合并的基础上, 应用遗传算法建立了以流水线平衡为目标的服装工序编排模型.关 键 词: 遗传算法; 流水线平衡; 服装中图分类号:TS941. 6文献标识码: A我国加入 WTO 后, 服装企业
2、面临新的机遇与挑战 1 : 配额的取消将使我国服装在价格上更具竞争力;而发达国家目前正努力进行产业结构的调整, 增加服装产业高科技含量; 一些新兴发展中国家如印度、越南等的劳动成本的竞争力也逐渐赶超我国. 我国传统的成本优势及低价策略正越来越失去作用. 因此与现代科学技术相结合, 提高企业的竞争力势在必行.服装工序编排优化是反映在一定数量的工作地条件下, 流水线能获得最大的产量且生产周期最短; 或指能达到一定的日产量, 流水线所设置的工作地数量最少. 所以根本问题是要提高操作工人的有效工时, 减少无效工时, 从而达到流水线生产均衡 2 . 目前在机械、电子等行业已采用模拟退火、遗传算法等技术进
3、行生产线优化和流水生产调度等问题设计, 提高了设计的速度和准确性. 在服装行业这方面研究甚少. 本文基于遗传算法来研究服装工序编排的优化.1 问题的描述要达到流水线平衡, 减少无效工时, 在于各工作地的负荷是否一致, 即每人承担的工序时间基本一致.每人平均加工时间( S . P . T ) = 标准总加工时间T A 作业人数 N由于每个工序所用时间不一致, 分配给每人承担的工序时间不可能与平均每人加工时间( S. P . T 即平均节拍) 一致. 如何才能使每人承担的工序时间基本一致, 就是本文研究的内容. 我们先来确定较理想的上、下限. 上限: U. P . T = S. P . T A0.
4、 95; 下限: L . P. T = S . P . T - ( U. P . T - S. P . T ) = 2S . P. T - U. P. T .本文研究的工序编排优化问题的条件为: ( 1) 各加工工序时间已知; ( 2) 各加工工序顺序已知; ( 3) 各加工工序所用的设备已知; ( 4) 一个工序可由不同的操作人员负责; ( 5) 每一操作人员尽量使用一台加工设备进行加工; ( 6) 每个人员同时只能加工一个工序, 而且只有当前工序完工后才能开始下一工序的加工; ( 7) 设备的种类和数量足够多; ( 8) 流水线的操作人数已知, 从而可以得出平均节拍时间 S. P . T
5、; ( 9) 操作人员的操作水平系数( 即操作的熟练程度) 已知.2 服装工序流程图及其计算本文所需的工序流程图包含设备类型、加工时间、紧前工序等, 如图 1( 为某一男式衬衫的节选) 所示 1 . 根据工序流程图可算出单件产品的总加工时间 T , 所需设备的种类 M 及每类设备的总需时间Tk ( k = 1 ,M) . 再根据 S . P . T 可得出要达到平衡每类设备所必须的工人数: Mk = Tk A S . P. T .如图 1 中, T = 33+38+ 23+ , ,+ 96=592 秒;S . P . T = 592 A7= 84. 6秒( 假设作业人数 N 为 7) ; U.
6、P . T = 84. 6 A0. 95= 89.1 秒; L . P. T = 2 84.6- 89. 1= 80. 1 秒; 所需设备的种类 M = 3 类( 1. 手工熨斗; 2. 平缝机; 3. 五线包缝机) ; 每类设备的时间为 T 1 = 186收稿日期: 2003- 06- 27作者简介: 楼亚芳( 1977- ) , 女, 浙江东阳人, 硕士生. 4 .第 4 期楼亚芳: 基于遗传算法的服装工序编排规划# 51 #图 1某一男衬衫工序流程图节选秒; T 2= 310 秒; T 3= 96 秒.在进行工序的合理分配之前需对相连小工序( 同种设备加工, 且其加工时间相加小于等于(
7、S. P . T ) 进行合并、大工序( 其加工时间大于 U . P. T ) 进行拆分,工序号重编.如图 1 中, 相连的 1 号工序和 2 号工序其加工设备均为手工熨斗, 又因其加工时间为 33+ 38 89. 1, 可将其分为成两个工序, 即一个工序为 89. 1 秒, 另一工序为 6. 9 秒( 也就是说该工序上的 89. 1/ 96= 93% 的产量为一工人操作, 剩下 7% 的量由另一工人操作) . 按此所得的新工序图如图 2 所示.图 2某一男衬衫拆分、合并后的工序流程图节选3 工序编排的优化3. 1个体表示在实际工厂里, 不是每人只操作一台设备, 而是大部分人只操作一种设备(
8、有利于提高工人熟练程度) , 而小部分人则为多功能型, 即能操作多种设备. 每种设备的人员数为: Mk = Tk A S. P. T , k = 1, , M. 则余M下的 N -2 Mk 的人员为多功能型 3 . 再来看看本文k= 1的例子. M 1= 186 A 84. 6= 2; M2= 310 A 84. 6= 3; M3= 96 A84. 6= 1, 即有2 人专门进行手工熨烫, 3 人专门进行平缝机操作, 1 人专门操作五线包缝机. 余下的 7-( 2+ 3+ 1) = 1 为多功能型, 即能操作所有设备.本文用二维矩阵 S = Sij N L 表示个体 3 , 其中N 表示工人数
9、, L 表示拆分、合并后的总操作数. 除零矩阵元素外, 任一矩阵元素值均不相等. 且每一非零矩阵元素( 称非零元素) 值表示工序号, 即图 2 中的工序号. 在矩阵 S 中, 无用零元素都在行右, 即v SiKj X0, 且NSiu= 0( i = 1, 2, , N ) ; u= Kj + 1, , L ) , i=21di = L ( di 为S 中第i 行上非零元素的个数) .个体满足可行解的条件为: ( 1) 设备约束: 每一操作必须在其相应的设备上加工, 这儿也可说对人员的约束, 因人员与设备已对应好. 零元素可在任意设备上加工. ( 2) 操作顺序的约束: 任一工序的列号小于其紧前
10、工序的列号.3. 2初始群体的设定(1) 先给任一个体矩阵 S 置零, 然后按照如下步骤随机给 L 个矩阵元素值不同( 1- L ) 的整数值, 且满足可行解的约束条件for P: = 1 to L do根据图 2, if p 无紧前工序 then 根据 p 的操作类型, 随机产生可供使用的行号( 工人及相应的设备) i 并在( 1, w ) 内随机产生列号 j ( w 为该工序之后的总工序数) , 置 Sij = p , else( 即 p 为中间工序或最后工序) 根据 p 的操作类型, 随机产生可供使用的行号( 工人及相应的设备) h , 并在 S 中找到p 的紧前工序种的最大列号g, 在
11、 g+ 1, L - v 中随机产生一列号 t ( v) 为该工序的后总工序数) , 置 Sht = P endfor( 2) 通过立体搜索, 前移个体矩阵中的非零元素.对个体矩阵 S 逐行( 行号 i 从 1 到( i + 1) mod N)逐列( 列号 j 从 1 或断点到 L ) 扫描非零元素 Sij , 若 Sij 无紧前工序则前移到本行的第一个零元素处( 互换) 并置前移标志, 否则 判工序 Sij 的紧前工序是否均已前移过, 若均前移过则由 j 向左找紧前工序的最大列号 t ( t j ) , 将 Sij 前移到i 行 t 列后的第 1 个零元素处( 互# 52 #中原工学院学报2
12、003 年第 14 卷换) ; 若有紧前工序未前移过则把 Sij 作断点, 扫描下一行 等直到 S 中的L 个非零元素全部前移, 而无用零移到行右.3. 3适应值的计算设 t ( Sij ) 为个体 S 中工序Sij 的运行时间, 则每一L工人的总加工时间 Li = ki j =21 t( Sij ) , i = 1, , N . 其中k i 为工人i 的操作熟练程度系数, 为已知数.N+ L 2+ ,LN ) /个体 S 的适应值f = mini=21 L - ( L 1N 2/ N群体中求得的最小适应值即为每人总加工时间的方差.3. 4选择算子置初始群体规模为偶数, 将每代群体按适应值降序
13、排序. 取排在前 50% 的个体复制到下一代, 余下的个体进行变异, 若变异不成功, 则作为下一代保存, 否则将产生的子个体经立体搜索, 前移非零元素后保存到下一代 4 .3. 5变异算子本文只有变异算子而没有用交叉算子. 为了使个体经变异后能满足操作顺序约束要求, 须先求需要移动的工序之移动区 3 .设个体 S 中元素Sij 的移动区间为开区间( wt , wr ) ; wt 为该工序的紧前工序中最大的列号, wr 为紧后工序的列号. 当 Sij = 0 时, 其移动区长度为( 0, L + 1) , 故不用求零元素的移动区.将需要变异的个体, 随机选择如 2 种变异算子中的一种进行变异.(
14、1) ( a) 在个体 S 中, 随机选择一个非零元素 Sij , ( b) 获得其移动区( a1, a2) , 在( a1, a2) 内随机产生一列号 k , 并随机产生一可加工 Sij 的行号( 人员) i( t X i, 若 t = i 重新产生t, 或只有 t = i, 重找 Sij , 转( b) . 若求得Stk 的移动区( a3, a4) 包含 Sij ( a3 j a4) , 则可互换 Sij 和Stk . ( Stk 值可为 0) .(2) 将个体中操作数量多行上的一个非零元素与其移动区内的另一可加工其操作类型行上的零元素互换.4结 语通过上述流水线编排规划模型的建立, 可以
15、此为基础进行计算机流水线编排的系统设计, 大大提高流水线编排效率, 同时也克服了流水线编排必须由专业人员进行的缺点, 提高了企业的竞争力.参考文献: 1 赵岚. 服装生产流水线仿真技术研究 D . 上海: 东华大学图书馆, 2002. 2 许树文, 张文斌. 微型计算机辅助服装缝纫流水线优化设计 J . 中国纺织大学学报, 1992, 18( 6) : 43- 50. 3 翁妙凤. 解 Job- shop 调度问题的混合模拟退火进化规划 J . 信息与控制, 1999, 28( 2) : 81- 85. 4 王小平, 曹立明. 遗传算法M . 西安: 西安交通大学出版社, 2002.Garme
16、nt Procedure Scheduling Based on Gentic AlgorithmsLOU Ya-fang( Donghua University, Shanghai 200051, China)Abstract: The paper first discusses the importance of setting up the system of arranging garment working procedure, and then based on the split and combination of garment working procedure, sets up a model with genetic algorithms aiming at the line balancing.Key words:genetic algorithms; line balancing; garment