第8期 陈晓慧等：基于遗传算法的可重入钢管生产优化调度 。1071。 dergrouping pmoblem.Ind Eng Manage.2004(1):86 机器4 M34☐ 3 (李虎.霍佳震.钢管生产的合同组批优化算法.工业工程与 管理，20041)：86 M4 33 [3 Lu F.Tian G H.Solving scheduling problems of molling sequence M 3 3□ with an adaptive genetic algorithm.J Shandong Univ Eng Sci, 3352 2003.33(3):311 (路飞，田国会.用自适应遗传算法求解轧制顺序调度问题 M 354321 山东大学学报：工学版，2003,33(3)：311) 0 10 15 20 25 30 [4 Chen C W,Dong S H.Ding W E.Optimization of multi-stage 时间h ☐工件形测工件形圆工件用工件用， production planning in ERW pipe manufacturing.J Univ Sci ①1表示加工时间 Technol Bejing,2006.28(7):691 (陈超武，董绍华，丁文英.ERW钢管多阶段生产计划的编制 及优化.北京科技大学学报，2006,28(7)：691) 图3最大完成时间的Pareto解的甘特图 [5 Zhong H Y.Hu JZ.A heuristic algorithm for steel pipes pro Fig.3 Gantt of maximum completion time based on Pareto duction scheduing.Ind Eng Manage,2008(2):80 表3Pato最优解与SPT规则解的工件完工时间。 (钟海嫣.霍佳震.钢管冷区生产调度的一种启发式算法.工 业工程与管理.2008(2)：80) Table3 Work competion time co by Pareto and SPT mules [6 Cui J S,Li T K,Zhang W X.Hybrid fbw shop scheduling model 工件W Pareto最优解的C。 SPT规则的c。 and its genetic algorithm.J Univ Sci Technol Bjing.2005.27 W (5):623 29 27 (崔建双，李铁克，张文新.混合流水车间调度模型及其遗传 W2 26 26 算法.北京科技大学学报.2005,27(5)：623) W3 22 23 [7 Kumar P R.Re-entrant lines.Queuing Syst,1993.13(1/3): W 28 29 87 [8 Wang Y,Wu Z M,Sui Y.Scheduling re entrant manufacturing Pareto的遗传算法相比SPT规则的各工件完工时 lines of semiconductor based on GA.Comnput Simul,2007.24 间更符合合同交货期，交货期满意度指标更有优势. (12):247 (王永，吴智铭，隋义。基于遗传算法的可重入半导体生产线 由此可见，基于Pareto的混合遗传算法在钢管可重入 的调度.计算机仿真.2007.2412)：247) 生产的计划与调度优化问题上可行和合理，有较好的 9Reeves C R.A genetic algorithm for flow shop sequencing.Com- 优化性能，算法的求解速度快，结果具有可操作性. pu1 Oper Res,1995,22(1):5 [10 Chen CL Vempati V S.Aljaber N.An application of genetic 5结论 algorit hms for flow shop problems EurJ Oper Res,1995,80: 389 可重入生产系统不仅在冷拔无缝钢管生产，而 11]Deng K,Lin J,Wang F.Scheduling of re-entrant lne based on swarm intelligence//2008 Inter national Symposium on Knowl 且在机械加工、半导体生产等制造系统中广泛存在. edge Acquisition and Modeling.Wuhan.2008:323 本文研究可重入钢管生产的优化调度问题，把若干 12]Zhu X J.Pan D.Wang A L,et al.Multiobjective optimization 参数相同的工件组为一批，设定规则把组批的钢管 design with mixeddiscrete variables in mechanical engineering via Pareto genetic algorithm.J Shanghai Jicotong Univ,2000, 看作单个加工工件，以最后完工时间、交货期满意 343):411 度、机器总负荷建立多目标优化函数，并对每一目标 (朱学军，攀登，王安麟，等混合变量多目标优化设计的 建立数学模型，采用基于Pareto的混合遗传算法对 Pareto遗传算法实现.上海交通大学学报，2000,34(3)： 411) 模型进行优化求解.为适应可重入生产系统的要 13 Wu X L,Sun S D.Yu JJ,et al.Research on multi-obiective 求，遗传算法采用两层编码结构，并将关键路径网络 optimization for flexible job shop scheduling.Comput Integr 图应用到染色体的编码及解码中，选择策略集成了 Manuf Sys1,2006.12(5):731 (吴秀丽，孙树栋，余建军，等。多目标柔性作业车间调度优 精英保留策略和小生境技术，从而保证了解的多样 化研究.计算机集成制造系统.2006.12(5)：731) 性.应用算例的结果表明，相比SPT优化规则，基于 14 Gu F,Chen H P,Lu B Y.The soution for multi-objective flex- Pareto的遗传算法对优化调度有更好的优化性能. ibk job shop scheduling based on genet ic algorithm.Oper Res Manage Sci,2006.15(1):B4 参考文献 (古蜂，陈华平，卢冰原.基于遗传算法的多目标柔性工作车 间调度问题求解.运筹与管理，2006.15(1)：134 [1]Tang LX.Zhang G F,Yang Z H,et al.Research on hot rolling 15]Yu Q W.Zhao L Pan S X.A scheduling optimization of flexi- scheduling for tube production.Iron Steel,1999.34(4):73. bl jolrshop using genetic algrithm.Modular Mach Tool Au- (唐立新，张国范，杨自厚，等.热轧钢管轧批排序模型及算 tom Manuf Tech,2004(4):32 法.钢铁，1999.344)：73) (余琦玮，赵亮，潘双夏.基于遗传算法的柔性作业车间调度 [2 Li H.Huo Z J.A heuristic akorithm for seamless stee tube or- 优化.组合机床与自动化加工技术，2004(4)：32)图 3 最大完成时间的Pareto 解的甘特图 Fig.3 Gantt of maximum completion time based on Paret o 表 3 Pareto 最优解与S PT 规则解的工件完工时间 co Tabl e 3 Work completion time co by Paret o and S PT rules 工件 W Pareto 最优解的 co SPT 规则的 co W1 29 27 W2 26 26 W3 22 23 W4 28 29 Pareto 的遗传算法相比 SPT 规则的各工件完工时 间更符合合同交货期, 交货期满意度指标更有优势 . 由此可见, 基于 Pareto 的混合遗传算法在钢管可重入 生产的计划与调度优化问题上可行和合理, 有较好的 优化性能, 算法的求解速度快, 结果具有可操作性. 5 结论 可重入生产系统不仅在冷拔无缝钢管生产, 而 且在机械加工、半导体生产等制造系统中广泛存在 . 本文研究可重入钢管生产的优化调度问题, 把若干 参数相同的工件组为一批, 设定规则把组批的钢管 看作单个加工工件, 以最后完工时间 、交货期满意 度、机器总负荷建立多目标优化函数, 并对每一目标 建立数学模型, 采用基于 Pareto 的混合遗传算法对 模型进行优化求解.为适应可重入生产系统的要 求, 遗传算法采用两层编码结构, 并将关键路径网络 图应用到染色体的编码及解码中, 选择策略集成了 精英保留策略和小生境技术, 从而保证了解的多样 性.应用算例的结果表明, 相比 SPT 优化规则, 基于 Pareto 的遗传算法对优化调度有更好的优化性能 . 参 考 文 献 [ 1] Tang L X, Zhang G F, Yang Z H, et al.Research on hot rolling scheduling for tube production.Iron S teel, 1999, 34( 4) :73. ( 唐立新, 张国范, 杨自厚, 等.热轧钢管轧批排序模型及算 法.钢铁, 1999, 34( 4) :73) [ 2] Li H, Huo Z J.A heuristic algorithm f or seamless steel tube or￾der-grouping problem .Ind Eng Manage, 2004( 1) :86 ( 李虎, 霍佳震.钢管生产的合同组批优化算法.工业工程与 管理, 2004( 1) :86) [ 3] Lu F, Tian G H .Solving scheduling problems of rolling sequence w ith an adaptive geneti c algorithm .J Shandong Uni v Eng Sci, 2003, 33 ( 3) :311 ( 路飞, 田国会.用自适应遗传算法求解轧制顺序调度问题. 山东大学学报:工学版, 2003, 33 ( 3) :311) [ 4] Chen C W, Dong S H, Ding W E .Optimization of multi-stage production planning in ERW pipe manuf acturing .J Uni v Sci Technol Bejing , 2006, 28( 7) :691 ( 陈超武, 董绍华,丁文英.ERW 钢管多阶段生产计划的编制 及优化.北京科技大学学报, 2006, 28( 7) :691) [ 5] Zhong H Y, Huo J Z .A heu ristic algorithm for st eel pipes pro￾duction scheduling .Ind Eng Manage, 2008( 2) :80 ( 钟海嫣, 霍佳震.钢管冷区生产调度的一种启发式算法.工 业工程与管理.2008( 2) :80) [ 6] Cui J S, Li T K, Zhang W X.Hybrid flow shop scheduling model and its genetic algorithm .J Uni v S ci Technol Bejing , 2005, 27 ( 5) :623 ( 崔建双, 李铁克, 张文新.混合流水车间调度模型及其遗传 算法.北京科技大学学报, 2005, 27( 5) :623) [ 7] Kumar P R.Re-entrant lines.Queuing Syst , 1993, 13( 1/ 3 ) : 87 [ 8] Wang Y, Wu Z M , Sui Y .Scheduling re-entrant manuf acturing lines of semiconduct or based on GA.Com put Simu l, 2007, 24 ( 12) :247 ( 王永, 吴智铭, 隋义.基于遗传算法的可重入半导体生产线 的调度.计算机仿真, 2007, 24( 12) :247) [ 9] Reeves C R.A geneti c algorithm f or flow shop sequencing .Com￾pu t Oper Res, 1995, 22( 1) :5 [ 10] Chen C L, Vempati V S , Aljaber N.An application of genetic algorithms f or flow shop problem s.Eur J Oper Res, 1995, 80: 389 [ 11] Deng K, Lin J, Wang F .Scheduling of re-entrant line based on swarm int elligence ∥2008 Inter national Sym posium on Knowl￾edge Acquisition and Modeling.Wuhan, 2008:323 [ 12] Zhu X J, Pan D, Wang A L, et al.Multiobjective optimization design w ith mixed-discret e variables in mechanical engineering via Pareto genetic algorithm .J S hanghai Jiaotong Uni v, 2000, 34( 3) :411 (朱学军, 攀登, 王安麟, 等.混合变量多目标优化设计的 Paret o 遗传算法实现.上海交通大学学报, 2000, 34( 3 ) : 411) [ 13] Wu X L, S un S D, Yu J J, et al.Research on multi-objecti ve optimization for flexible job shop scheduling .Comput Int egr Manu f S yst, 2006, 12( 5) :731 ( 吴秀丽, 孙树栋, 余建军, 等.多目标柔性作业车间调度优 化研究.计算机集成制造系统.2006, 12( 5) :731) [ 14] Gu F, Chen H P, Lu B Y .The solution for multi-objecti ve flex￾ible job shop scheduling based on genetic algorithm .Oper Res Manage S ci, 2006, 15( 1) :134 ( 古峰, 陈华平, 卢冰原.基于遗传算法的多目标柔性工作车 间调度问题求解.运筹与管理, 2006, 15( 1) :134) [ 15] Yu Q W, Zhao L, Pan S X.A scheduling optimization of flexi￾ble job-shop using genetic algorithm .Modu lar Mach Tool Au￾tom Manu f Tech , 2004(4) :32 ( 余琦玮, 赵亮, 潘双夏.基于遗传算法的柔性作业车间调度 优化.组合机床与自动化加工技术, 2004( 4) :32) 第 8 期 陈晓慧等:基于遗传算法的可重入钢管生产优化调度 · 1071 ·