基于粒子群算法的混合装配线计划调度系统研究
|
摘要
对生产作业调度进行优化可以提高企业生产资源的利用率和企业的生产效率,有效的调度算法是生产调度领域的重要研究方向。作为一种新的进化类仿生算法,粒子群优化方法目前主要应用于求解连续空间域的优化问题。调度问题是一类求解比较困难的典型组合优化问题,本文则把粒子群算法与遗传算法相结合组成协同优化算法应用到调度问题中,提高了以总装时间最小为优化目标的多品种混合计划调度系统的优化能力。
目前我国在多品种混合装配线计划调度方面的研究上存在很多不足,系统编排的生产作业调度计划效率低下。因此本文考虑实际的需求和针对以往系统的不足,对多品种混合装配线进行了研究和相应系统的改进,主要工作如下:
1.针对以往研究模型的不足,并且为了缩短产品装配周期,准时交货,本文提出以任务总装时间最小为目标的作业分配与产品排序同时优化的模型,在模型约束中充分考虑总装过程实际情况中多约束(包括作业优先关系、物料齐备、工位数目、固定资源、流动资源、人员工种等约束)。
2.粒子群算法速度公式中的参数对其搜索能力影响很大,因此本文将混沌优化技术应用到其速度公式参数的优化中。本文将改进后的粒子群算法对计划调度的多个典型例子进行优化最终都能得到最优结果,说明引入混沌技术后的粒子群算法提高了其全局收敛性,最大可能地找到全局最优解。
3.本文针对以往算法的不足,提出了基于PSO的产品排序和基于GA的作业分配的PSO协同优化算法,PSO协同优化算法通过对实际算例优化总装时间得到的最小总装时间只有基于GA的作业分配和产品排序协同优化的算法得到的最小总装时间的50%~80%,这说明PSO协同优化算法极大的提高了计划调度系统的性能。
4.本文针对目前市场上产品更新换代迅速的情况,建立了紧急任务插入情况下的计划调度系统模型,并在多品种混合装配线计划调度系统的改进过程中开发了二次混流计算模块。
It is possible to enhance the production efficiency of the enterprise and its resource utilization by optimizing the planning and scheduling of production, the effective scheduling algorithm is an important research direction in the production scheduling field. As one kind of new evolution biological algorithm, presently particle swarm algorithm is mainly applied to solving the optimizing problem in the continual space. The scheduling problem is a kind of combination optimization question which is hard to solve; In this thesis particle swarm algorithm is applied in the process of planning and scheduling and combined with genetic algorithm to form the collaborative optimization which is to be applied in the scheduling problems. This can enhance the optimizing efficiency of Mixed-Model Assembly Line whose goal is the minimization of the whole assembly time.
At present our country does not do sufficient research on Mixed-Model Assembly Line and the efficiency of scheduling plan produced by computer is very low. Considering the actual demand and the insufficiency of former system, research is done to improve the corresponding system of Mixed-Model Assembly Line in this thesis; the prime task is as follows:
1. Because of the insufficiency of the former research model and in order to reduce the product assembly cycle, he punctual delivery. This article proposed a model which is aimed at the minimal tasks assembly time. The model requests not only the integration of the plan and scheduling but the optimization of the job assignment and product sequencing. The multiple restraints in the actual situation are fully considered in the model restraint (including work precedence relation, material prepared, restraints and so on location number, fixed resources, flowing resources, personnel kind of work in a factory.).
2. The parameters in the velocity formula of the particle swarm optimization play an important role in its searching ability. Chaos technology is applied in the optimizing process of the parameters in the velocity formula, which enhances the global convergence and helps find the global optimal solution widest possibly.
3. Considering the shortcomings in the previous algorithm, the article proposes product sequencing based on PSO and PSO collaborative optimization for job assignment based on GA. The optimal result provides by the PSO collaborative optimization by optimizing the assembly time through the practical calculation example is only 50 to 80percent of the optimal result provides by collaborative optimization based on the GA job assignment and product sequencing. This means that PSO collaborative optimization CAN greatly enhance the property of the planning scheduling system.
4. Planned dispatching system model is established in the emergency task insertion situation, and module with two interflow computations is developed in the multi-variety mix assembly line improvement process.
目前我国在多品种混合装配线计划调度方面的研究上存在很多不足,系统编排的生产作业调度计划效率低下。因此本文考虑实际的需求和针对以往系统的不足,对多品种混合装配线进行了研究和相应系统的改进,主要工作如下:
1.针对以往研究模型的不足,并且为了缩短产品装配周期,准时交货,本文提出以任务总装时间最小为目标的作业分配与产品排序同时优化的模型,在模型约束中充分考虑总装过程实际情况中多约束(包括作业优先关系、物料齐备、工位数目、固定资源、流动资源、人员工种等约束)。
2.粒子群算法速度公式中的参数对其搜索能力影响很大,因此本文将混沌优化技术应用到其速度公式参数的优化中。本文将改进后的粒子群算法对计划调度的多个典型例子进行优化最终都能得到最优结果,说明引入混沌技术后的粒子群算法提高了其全局收敛性,最大可能地找到全局最优解。
3.本文针对以往算法的不足,提出了基于PSO的产品排序和基于GA的作业分配的PSO协同优化算法,PSO协同优化算法通过对实际算例优化总装时间得到的最小总装时间只有基于GA的作业分配和产品排序协同优化的算法得到的最小总装时间的50%~80%,这说明PSO协同优化算法极大的提高了计划调度系统的性能。
4.本文针对目前市场上产品更新换代迅速的情况,建立了紧急任务插入情况下的计划调度系统模型,并在多品种混合装配线计划调度系统的改进过程中开发了二次混流计算模块。
It is possible to enhance the production efficiency of the enterprise and its resource utilization by optimizing the planning and scheduling of production, the effective scheduling algorithm is an important research direction in the production scheduling field. As one kind of new evolution biological algorithm, presently particle swarm algorithm is mainly applied to solving the optimizing problem in the continual space. The scheduling problem is a kind of combination optimization question which is hard to solve; In this thesis particle swarm algorithm is applied in the process of planning and scheduling and combined with genetic algorithm to form the collaborative optimization which is to be applied in the scheduling problems. This can enhance the optimizing efficiency of Mixed-Model Assembly Line whose goal is the minimization of the whole assembly time.
At present our country does not do sufficient research on Mixed-Model Assembly Line and the efficiency of scheduling plan produced by computer is very low. Considering the actual demand and the insufficiency of former system, research is done to improve the corresponding system of Mixed-Model Assembly Line in this thesis; the prime task is as follows:
1. Because of the insufficiency of the former research model and in order to reduce the product assembly cycle, he punctual delivery. This article proposed a model which is aimed at the minimal tasks assembly time. The model requests not only the integration of the plan and scheduling but the optimization of the job assignment and product sequencing. The multiple restraints in the actual situation are fully considered in the model restraint (including work precedence relation, material prepared, restraints and so on location number, fixed resources, flowing resources, personnel kind of work in a factory.).
2. The parameters in the velocity formula of the particle swarm optimization play an important role in its searching ability. Chaos technology is applied in the optimizing process of the parameters in the velocity formula, which enhances the global convergence and helps find the global optimal solution widest possibly.
3. Considering the shortcomings in the previous algorithm, the article proposes product sequencing based on PSO and PSO collaborative optimization for job assignment based on GA. The optimal result provides by the PSO collaborative optimization by optimizing the assembly time through the practical calculation example is only 50 to 80percent of the optimal result provides by collaborative optimization based on the GA job assignment and product sequencing. This means that PSO collaborative optimization CAN greatly enhance the property of the planning scheduling system.
4. Planned dispatching system model is established in the emergency task insertion situation, and module with two interflow computations is developed in the multi-variety mix assembly line improvement process.
引文
[1]曹振新,朱云龙,赵明扬,等.混流装配线负荷平衡与投产排序的优化研究.信息与控制,2004,33(6):660~664.
[2]周亮.装配线平衡的最优化模型与算法研究.南京:南京理工大学博士学位论文,2005.
[3]王英明.单件小批车间作业计划与调度监控集成系统的研究与应用.广州:广东工业大学硕士学位论文,2003.
[4] Thomopoulos N T. Line Balancing-sequencing for Mixed-model Assembly. Management Science,1967,14(2): 59~75.
[5] Thomopoulos N T. Mixed Model Line Balancing with Smoothed Station Assignments. Management Science , 1970,16(9):593~603.
[6] Thomopoulos N T. Mixed Model Line Balancing with Smoothed Station Assignments. Management Science , 1970,16(9):593~603.
[7] Gokcen H, Erel E. Binary Integer Formulation for Mixed-model Assembly Line Balancing Problem. Computers & Industrial Engineering, 1998, 34(2):451~461.
[8]罗耀辉.车间作业计划调度系统的研究与开发.西安:西北工业大硕士学位论文,2003.
[9]刘志刚.基于敏捷模式的生产车间计划与调度系统研究.西安:西安理工大学硕士学位论文,2006.
[10] Merengo C, Nava F, Pozzetti A. Balancing and Sequencing Manual Mixed-model Assembly Lines. International Journal of Production Researches, 1999, 37(12): 2835~2860.
[11] Kim Y K, Kim S J, Kim J Y. Balancing and Sequencing Mixed model U-lines with a Co-evolutionary Algorithm. Production Planning and Control, 2000, 11 (8): 754~764.
[12] Miltenburg J. Balancing and Scheduling Mixed-model U-shaped Production lines. The International Journal of Flexible Manufacturing Systems, 2002, 14(2): 119~151.
[13]罗卓.装配线平衡系统研究与开发.广州:广东工业大学硕士学位论文,2006.
[14] Bard J F, Dar-EI E, Shtub A. An analytic Framework for Sequencing Mixed-model Assembly Lines. International Journal of Production Research, 1992, 30(1): 35~48.
[15] Yow Y L, Matheson L A. Sequencing Mixed-model Assembly Lines with Genetic Algorithms .Computers & Industry Engineering, 1996, 30(4): 1027~1036.
[16] Sumicharst RT. A Comparative Analysis of Sequencing Procedures for Mixed-model Assembly Lines in A Ust-in-time Production System. International Journal of Production Research, 1992,30(1): 199~214.
[17]林献坤,李爱平,陈炳森.混合粒子群算法在混流装配线优化调度中的应用.工业工程与管理,2006,1(1):53~57.
[18]田志友,田澎,王浣尘.混流装配线调度问题的离散粒子群优化解.工业工程与管理,2005,6(1):53~57.
[19]宋华明,韩玉启.混合装配线上物料供应的平准化排序.系统工程,2002,20(3):15~19.
[20]李斌,陈立平,黄正东.面向大规模定制的装配线优化调度研究.中国机械工程,2005,16(24):2198~2202.
[21]肖建华,肖田元,赵银燕.遗传禁忌搜索算法在混流装配线排序中的应用.工业工程与管理,2003,2(1):14~17.
[22]赵伟,韩文秀,罗永泰.准时生产方式下混流装配线的调度问题.管理科学学报,2000,3(4):23~28.
[23] Yeo Keun Kim, Chul Ju Hyun, Yeongho. Sequencing In Mixed-model Assembly Lines: A Genetic Algorithm Approach. Computers Ops Res, 1996, 23(12):1131~1145.
[24]卫东,金烨.给定序列的混合品种装配生产线平衡算法.机械工程学报,2004,40(4):135~138.
[25]陆叶,苏平.混合装配线平衡问题的建模与分析.机电产品开发与创新,2007,20(5):110~112.
[26]皮兴忠,范秀敏,严隽琪.用基于作业序列的遗传算法求解装配线平衡问题.机械科学与技术,2003,22(1):35~38.
[27]钟求喜.任务分配与调度的共同进化方法.计算机学报,2001,24(3):308~314.
[28]陈琪峰.导弹总体参数优化设计的合作协同进化MDO算法.国防科技大学学报,2001,23(5):9~12.
[29]刘光惠,韦日钰.行架拓扑和尺寸优化的协同演化算法.广西科学,2002,7(2): 81~84.
[30] Kennedy J,Eberhart R C. Particle Swarm Optimization. Proceedings of IEEE International Conference on Neutral Networks,Perth,Austarlia1995,1942~1948.
[31] Young-Man Park,Kap Hwan Kim. A Scheduling Method of Berth and Quay Crnaes. OR Spectrum (2003)25:l~23.
[32]王筠,马柯,冯涛.自适应免疫遗传算法在混合流程车间调度中的应用.西安工程科技学院学报,2005,19 (1):79~81.
[33]吴启迪,汪镭.智能微粒群算法研究及应用.江苏教育出版社,2005:63~65.
[34]闭应洲,丁立新.交叉算子与免疫算子的作用比较.计算机工程,2007,8(1):170~174.
[35]云庆夏.进化算法.北京:冶金工业出版社,2000:1~200.
[36] F van den Bergh. An analysis of particle swarm optimizers.PHD dissertation. South Africa: Department of Computer Science, University of PREteria,2002.
[37] May R. Simple mathematical models with complicated dynamics. Nature(S0028-0836),1976, 261(5560): 459~467.
[38] Trelea I C. The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters (S0020-0190), 2003, 85(6):317~325.
[39] Naka S, Genji T, Yura T, et al. A hybrid particle swarm optimization for distribution state estimation. IEEE Transaction on Power Systems (S0885-8950), 2003, 18(1); 60~68.
[40] Maurice C, Kennedy J. The particle swarm-explosion, stability and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation (S1089-778X), 2002, 6(1): 58~73.
[41]刘志雄.调度问题中的粒子群优化方法及其应用研究.武汉理工大学工学博士学位论文,2005.
[2]周亮.装配线平衡的最优化模型与算法研究.南京:南京理工大学博士学位论文,2005.
[3]王英明.单件小批车间作业计划与调度监控集成系统的研究与应用.广州:广东工业大学硕士学位论文,2003.
[4] Thomopoulos N T. Line Balancing-sequencing for Mixed-model Assembly. Management Science,1967,14(2): 59~75.
[5] Thomopoulos N T. Mixed Model Line Balancing with Smoothed Station Assignments. Management Science , 1970,16(9):593~603.
[6] Thomopoulos N T. Mixed Model Line Balancing with Smoothed Station Assignments. Management Science , 1970,16(9):593~603.
[7] Gokcen H, Erel E. Binary Integer Formulation for Mixed-model Assembly Line Balancing Problem. Computers & Industrial Engineering, 1998, 34(2):451~461.
[8]罗耀辉.车间作业计划调度系统的研究与开发.西安:西北工业大硕士学位论文,2003.
[9]刘志刚.基于敏捷模式的生产车间计划与调度系统研究.西安:西安理工大学硕士学位论文,2006.
[10] Merengo C, Nava F, Pozzetti A. Balancing and Sequencing Manual Mixed-model Assembly Lines. International Journal of Production Researches, 1999, 37(12): 2835~2860.
[11] Kim Y K, Kim S J, Kim J Y. Balancing and Sequencing Mixed model U-lines with a Co-evolutionary Algorithm. Production Planning and Control, 2000, 11 (8): 754~764.
[12] Miltenburg J. Balancing and Scheduling Mixed-model U-shaped Production lines. The International Journal of Flexible Manufacturing Systems, 2002, 14(2): 119~151.
[13]罗卓.装配线平衡系统研究与开发.广州:广东工业大学硕士学位论文,2006.
[14] Bard J F, Dar-EI E, Shtub A. An analytic Framework for Sequencing Mixed-model Assembly Lines. International Journal of Production Research, 1992, 30(1): 35~48.
[15] Yow Y L, Matheson L A. Sequencing Mixed-model Assembly Lines with Genetic Algorithms .Computers & Industry Engineering, 1996, 30(4): 1027~1036.
[16] Sumicharst RT. A Comparative Analysis of Sequencing Procedures for Mixed-model Assembly Lines in A Ust-in-time Production System. International Journal of Production Research, 1992,30(1): 199~214.
[17]林献坤,李爱平,陈炳森.混合粒子群算法在混流装配线优化调度中的应用.工业工程与管理,2006,1(1):53~57.
[18]田志友,田澎,王浣尘.混流装配线调度问题的离散粒子群优化解.工业工程与管理,2005,6(1):53~57.
[19]宋华明,韩玉启.混合装配线上物料供应的平准化排序.系统工程,2002,20(3):15~19.
[20]李斌,陈立平,黄正东.面向大规模定制的装配线优化调度研究.中国机械工程,2005,16(24):2198~2202.
[21]肖建华,肖田元,赵银燕.遗传禁忌搜索算法在混流装配线排序中的应用.工业工程与管理,2003,2(1):14~17.
[22]赵伟,韩文秀,罗永泰.准时生产方式下混流装配线的调度问题.管理科学学报,2000,3(4):23~28.
[23] Yeo Keun Kim, Chul Ju Hyun, Yeongho. Sequencing In Mixed-model Assembly Lines: A Genetic Algorithm Approach. Computers Ops Res, 1996, 23(12):1131~1145.
[24]卫东,金烨.给定序列的混合品种装配生产线平衡算法.机械工程学报,2004,40(4):135~138.
[25]陆叶,苏平.混合装配线平衡问题的建模与分析.机电产品开发与创新,2007,20(5):110~112.
[26]皮兴忠,范秀敏,严隽琪.用基于作业序列的遗传算法求解装配线平衡问题.机械科学与技术,2003,22(1):35~38.
[27]钟求喜.任务分配与调度的共同进化方法.计算机学报,2001,24(3):308~314.
[28]陈琪峰.导弹总体参数优化设计的合作协同进化MDO算法.国防科技大学学报,2001,23(5):9~12.
[29]刘光惠,韦日钰.行架拓扑和尺寸优化的协同演化算法.广西科学,2002,7(2): 81~84.
[30] Kennedy J,Eberhart R C. Particle Swarm Optimization. Proceedings of IEEE International Conference on Neutral Networks,Perth,Austarlia1995,1942~1948.
[31] Young-Man Park,Kap Hwan Kim. A Scheduling Method of Berth and Quay Crnaes. OR Spectrum (2003)25:l~23.
[32]王筠,马柯,冯涛.自适应免疫遗传算法在混合流程车间调度中的应用.西安工程科技学院学报,2005,19 (1):79~81.
[33]吴启迪,汪镭.智能微粒群算法研究及应用.江苏教育出版社,2005:63~65.
[34]闭应洲,丁立新.交叉算子与免疫算子的作用比较.计算机工程,2007,8(1):170~174.
[35]云庆夏.进化算法.北京:冶金工业出版社,2000:1~200.
[36] F van den Bergh. An analysis of particle swarm optimizers.PHD dissertation. South Africa: Department of Computer Science, University of PREteria,2002.
[37] May R. Simple mathematical models with complicated dynamics. Nature(S0028-0836),1976, 261(5560): 459~467.
[38] Trelea I C. The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters (S0020-0190), 2003, 85(6):317~325.
[39] Naka S, Genji T, Yura T, et al. A hybrid particle swarm optimization for distribution state estimation. IEEE Transaction on Power Systems (S0885-8950), 2003, 18(1); 60~68.
[40] Maurice C, Kennedy J. The particle swarm-explosion, stability and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation (S1089-778X), 2002, 6(1): 58~73.
[41]刘志雄.调度问题中的粒子群优化方法及其应用研究.武汉理工大学工学博士学位论文,2005.