离散型制造企业的车间调度系统研究
|
摘要
随着市场竞争的加剧,企业生产正朝着多品种、小批量方向发展。在离散型企业尤其是机械行业,生产的产品品种多、批量小,生产组织工作复杂,特别是企业的生产作业计划安排工作难度很大,计划编制往往凭主观经验,计划的及时性、应变性差,导致产品生产周期长,在制品占用量大,机床利用效率低等,从而影响了多品种、小批量生产的经济效益。因此,研究离散型企业车间调度问题,不仅具有较大的理论意义,而且还有相当大的实用价值。
本文通过对离散型企业及其车间调度问题的详细分析和对调度理论进行深入的研究,提出了具有柔性加工路径的车间作业调度模型。这里的柔性是指设备安排的柔性,即工件的设备加工路径不是固定的和预先确定的,而是柔性的。系统采用遗传算法与启发式规则相结合的方法解决此类调度问题,具体方法是把这类问题的求解分解为两个优化本原问题的求解,一个是利用遗传算法为工序选择资源,一个是利用启发式规则决定机器上工序的加工次序和开始加工时间。
另外,系统充分考虑了生产中的不确定性因素,采用了周期性调度和再调度相结合的策略,扰动发生后,遗传算法能够根据动态数据库所提供的最新任务数据,快速产生新的优化方案。同时,为了提高系统的可视度和易读性,将虚拟现实技术应用其中,对调度系统中车间动态信息的实时监控做了初步的尝试。利用虚拟现实建模语言VRML实现了车间设备和车间布局简约模型的构建以及设备运行状态的表达。最终,开发了一个将静态计划和动态调度相结合,包括离线计划和动态调度的作业车间调度原型系统。
As market competition intensifies, enterprises are going towards the direction of multi-varieties and small-batch production. In discrete enterprises, especially those in the machinery industry, the case with multi-varieties and small-batch production and complex production organization, will cause long production period, mass work in process, inefficient use of machine tools and so on, thus affect the economic benefits of multi-varieties and small-batch production. The complexity of production organization particularly embodies in the great difficulty of enterprises' production planning, plan formulation based on subjective experience, and the poor timeliness and flexibilities of the plan. The research on Job-shop scheduling in the discrete manufacturing enterprises has important theoretical and practical significance.
Based on the deep research of scheduling theory and a detailed analysis of the discrete manufacturing enterprises and its scheduling problems, a model for Job-shop scheduling with alternative operation routes is put forward in the paper. The alternative operation routes refer to flexibility of machine arrangement, that is, one operation arranged on which machine is not fixed and predetermined but alternative. This paper adopts the method combining genetic algorithm and heuristic rules to solve the Job-shop scheduling problem with alternative operation routes. So the solution to the problem is changed into optimizing two sub-problems, one is using genetic algorithm to select resources for process and the other is adopting heuristic rules to determine the sequence and start time of process on a machine.
Moreover, by fully considering the uncertain factors in the production, a strategy by combining periodic scheduling and re-scheduling is adopted. According to the updated data in the dynamic database after disturbance occurs, the genetic algorithm can generate optimized production planning in response to the changes of the Job-shop. Meanwhile, in order to improve the visibility and legibility, a preliminary attempt has been done for the real-time monitoring of the workshop dynamic information in the scheduling system, with the application of virtual reality technology. By using of the virtual reality modeling language VRML, a simple model of the workshop equipment and workshop layout is set up and the expression of the equipment running station is done. Finally, a Job-shop scheduling prototype system, which combines the static scheduling and dynamic control and includes planning offline and dynamic scheduling, is developed.
本文通过对离散型企业及其车间调度问题的详细分析和对调度理论进行深入的研究,提出了具有柔性加工路径的车间作业调度模型。这里的柔性是指设备安排的柔性,即工件的设备加工路径不是固定的和预先确定的,而是柔性的。系统采用遗传算法与启发式规则相结合的方法解决此类调度问题,具体方法是把这类问题的求解分解为两个优化本原问题的求解,一个是利用遗传算法为工序选择资源,一个是利用启发式规则决定机器上工序的加工次序和开始加工时间。
另外,系统充分考虑了生产中的不确定性因素,采用了周期性调度和再调度相结合的策略,扰动发生后,遗传算法能够根据动态数据库所提供的最新任务数据,快速产生新的优化方案。同时,为了提高系统的可视度和易读性,将虚拟现实技术应用其中,对调度系统中车间动态信息的实时监控做了初步的尝试。利用虚拟现实建模语言VRML实现了车间设备和车间布局简约模型的构建以及设备运行状态的表达。最终,开发了一个将静态计划和动态调度相结合,包括离线计划和动态调度的作业车间调度原型系统。
As market competition intensifies, enterprises are going towards the direction of multi-varieties and small-batch production. In discrete enterprises, especially those in the machinery industry, the case with multi-varieties and small-batch production and complex production organization, will cause long production period, mass work in process, inefficient use of machine tools and so on, thus affect the economic benefits of multi-varieties and small-batch production. The complexity of production organization particularly embodies in the great difficulty of enterprises' production planning, plan formulation based on subjective experience, and the poor timeliness and flexibilities of the plan. The research on Job-shop scheduling in the discrete manufacturing enterprises has important theoretical and practical significance.
Based on the deep research of scheduling theory and a detailed analysis of the discrete manufacturing enterprises and its scheduling problems, a model for Job-shop scheduling with alternative operation routes is put forward in the paper. The alternative operation routes refer to flexibility of machine arrangement, that is, one operation arranged on which machine is not fixed and predetermined but alternative. This paper adopts the method combining genetic algorithm and heuristic rules to solve the Job-shop scheduling problem with alternative operation routes. So the solution to the problem is changed into optimizing two sub-problems, one is using genetic algorithm to select resources for process and the other is adopting heuristic rules to determine the sequence and start time of process on a machine.
Moreover, by fully considering the uncertain factors in the production, a strategy by combining periodic scheduling and re-scheduling is adopted. According to the updated data in the dynamic database after disturbance occurs, the genetic algorithm can generate optimized production planning in response to the changes of the Job-shop. Meanwhile, in order to improve the visibility and legibility, a preliminary attempt has been done for the real-time monitoring of the workshop dynamic information in the scheduling system, with the application of virtual reality technology. By using of the virtual reality modeling language VRML, a simple model of the workshop equipment and workshop layout is set up and the expression of the equipment running station is done. Finally, a Job-shop scheduling prototype system, which combines the static scheduling and dynamic control and includes planning offline and dynamic scheduling, is developed.
引文
[1]刘敏,鲁建厦.离散型制造企业物流管理信息系统研究.机械工程师,2003,第9期,30-34
[2]庞庆华,潘郁.多品种小批量生产环境下的柔性调度研究[J].南京工业大学学报,2003,25(2):65-69
[3]Graves S C.A Review of Production Scheduling[J].Operations Research,1981,29(4):646-675
[4]苑丽红.基于遗传算法的FMS计划调度方法研究[D].长春理工大学,2005,6
[5]范路桥,常会友,朱旭东.作业调度问题研究[J].现代计算机,2004(187):21-25
[6]余建国.Job-shop调度优化方法及其应用研究[D].西安理工大学,2005,3
[7]黄学文.制造执行系统(MES)的研究和应用[D].大连理工大学,2003,5
[8]陈国良,王煦法.遗传算法及其应用[M].人民邮电出版社(第1版),1996,1-30
[9]何霆,刘飞,马玉林等.车间生产调度问题研究[J]。机械工程学报,2000,36(5):97-102
[10]郭立夫.运筹学[M].长春:吉林大学出版社,2002,8
[11]Jeffcoat,David E,Robert L,Bulfin.Simulated annealing for resource- constrained scheduling[J].European Journal of Operational research,1993,70:43-51
[12]Momazeri M,Van Wassehove L.N.Analysis of scheduling rules of an FMS[J].International Journal Product Research,1990,28(4):785-790
[13]Glover F.Paths for Integer Programming and Links to Artificial Intelligence[J].Compute Operations,1986,13(5):533-549
[14]王凌,郑大钟.基于遗传算法的Job-shop调度研究进展[J].控制与决策,2001(11):21-25
[15]林海凡,李尔波,唐敦兵等.生产调度问题的启发式遗传算法[J].机械科学与技术,2000(2):790-792
[16]曾佑琴.面向中小配套型企业制造执行系统的凋度算法研究[D].重庆大学,2005,5
[17]Sim S K,Yeo K T,Lee W H.An expert neural network system for dynamic job shop scheduling.Int J of Prod Res,1994,32(8):1759-1773
[18]Jones Albert,Rabelo Kuis Yih,Yuehwern Y.A hybrid approach for real-time sequencing and scheduling.Int J of Comp Integ Manuf,1995,8(2):145-154
[19]Lee C Y,Piramuthu S,Tsai Y K.Job shop scheduling with a genetic algorithm and machine learning.Int J of Prod Res,1997,35(4):1171-1191
[20]陈荣兴,于明.混合型生产方式中动态调度问题的研究.工业工程与管理,2004,3:53-57
[21]高红,熊光愣.决策规则在仿真调度中的应用.控制与决策,1995,10(2):114-118
[22]陈伟达.基于杂合遗传算法的车间作业调度问题研究.南京:东南大学,2001
[23]王晓平,曹立明.遗传算法-理论、应用与软件实现.西安西安交通大学出版社,2002,1
[24]杨敬松.基于遗传算法的适应分布式生产模式车间计划调度的算法研究(硕).吉林长春理工大学计算机应用技术,2002
[25]De Jong K.A.An analysis of the behavior of genetic adaptive system:[Ph D Dissertation].Ann Arber:Univ.Microflims,1975
[26]王凌.车间调度及其遗传算法.北京:清华大学出版社,2003
[27]蔡自兴,徐光祜.人工智能及其应用.北京:清华大学出版社,2003
[28]张晴,饶运清.车间动态调度方法研究.质量·成本·管理,2003,41(461):39-41
[29]Szelde Elizabeth Kerr,Roger M.Knowledge-based reactive scheduling.Prod Plan & Contr,1994,5(5):124-145
[30]Nof S Y,Grant F H.Adaptive/predictive scheduling review and a general framework.Prod Plan & Contr,1991,2(4)..298-312
[31]Cott B J,Macchietto S.Minimizing the effects of batch process variability using on-line Schedule modification.Computers and Chemical Engineering,1989,13(1/2):105-113
[32]孙志峻.智能制造系统车间生产优化调度.南京:南京航空航天大学,2002
[33]Suresh V,Chandhuri D.Dynamic scheduling-Asurvey of research.Int J of Prod Econ,1993,32(1):53-63
[34]Kanet J J,Sridharan V.The electronic leistand,a new tool for shop scheduling.Manufacturing Review,1990,(3):161-170
[35]段新昱.虚拟现实基础与VRML程[M].北京:高等教育出版社,2004,3
[36]Shukla,C;Vazquez,M;Chen,F.F.Virtual manufacturing.,an overview[J].Computers &Industrial Engineering,Oct 1996,31(1/2),79-82
[37]Ward,J.Virtual manufacturing:really useful[J].Engineering,Jun 1998,239(6),48-52
[38]汪兴谦.VRML虚拟造型实战演练[M].中国水利水电出版社,2002.1
[39]ERKES J M,KENNY K B,LEWIS J W,SARACHAN B D,SOBOLEWSKIM W,SUM R N.Implementing shared manufacturing services on the world-wide Web[J].Communications of the ACM,February 1996,39(2)
[40]HOU Honglun,SUN Shouqian,PAN Yunhe.Cyber-design and Cyber-manufacturing,In:Proceedings of 3rd International Conference on CAID&CD,2000:400-405
[41]H V Kan,V G Duffy,C J Su.An Internet Virtual Reality Collaborative Environment for Effectvie Product Design[J].Computers in Industry,2001,45(2):197-213.
[42]刘战强,艾兴.虚拟制造技术及其应用的现状与发展展望[J].山东大学学报(工学版),2002,6,32(3):213-217
[43]Laus Peter Berier.Web- based Virtual Reality in Design and Manufacturing Applications.[EB/OL].http://www.vrl.umich.edu/berier/Papers/compit2000/WebB asedVR,htm,2001.
[44]晏文靖,王海艳,王汝传.基于VRML的网络虚拟制造技术的研究.2004.9,24(3):80-84
[2]庞庆华,潘郁.多品种小批量生产环境下的柔性调度研究[J].南京工业大学学报,2003,25(2):65-69
[3]Graves S C.A Review of Production Scheduling[J].Operations Research,1981,29(4):646-675
[4]苑丽红.基于遗传算法的FMS计划调度方法研究[D].长春理工大学,2005,6
[5]范路桥,常会友,朱旭东.作业调度问题研究[J].现代计算机,2004(187):21-25
[6]余建国.Job-shop调度优化方法及其应用研究[D].西安理工大学,2005,3
[7]黄学文.制造执行系统(MES)的研究和应用[D].大连理工大学,2003,5
[8]陈国良,王煦法.遗传算法及其应用[M].人民邮电出版社(第1版),1996,1-30
[9]何霆,刘飞,马玉林等.车间生产调度问题研究[J]。机械工程学报,2000,36(5):97-102
[10]郭立夫.运筹学[M].长春:吉林大学出版社,2002,8
[11]Jeffcoat,David E,Robert L,Bulfin.Simulated annealing for resource- constrained scheduling[J].European Journal of Operational research,1993,70:43-51
[12]Momazeri M,Van Wassehove L.N.Analysis of scheduling rules of an FMS[J].International Journal Product Research,1990,28(4):785-790
[13]Glover F.Paths for Integer Programming and Links to Artificial Intelligence[J].Compute Operations,1986,13(5):533-549
[14]王凌,郑大钟.基于遗传算法的Job-shop调度研究进展[J].控制与决策,2001(11):21-25
[15]林海凡,李尔波,唐敦兵等.生产调度问题的启发式遗传算法[J].机械科学与技术,2000(2):790-792
[16]曾佑琴.面向中小配套型企业制造执行系统的凋度算法研究[D].重庆大学,2005,5
[17]Sim S K,Yeo K T,Lee W H.An expert neural network system for dynamic job shop scheduling.Int J of Prod Res,1994,32(8):1759-1773
[18]Jones Albert,Rabelo Kuis Yih,Yuehwern Y.A hybrid approach for real-time sequencing and scheduling.Int J of Comp Integ Manuf,1995,8(2):145-154
[19]Lee C Y,Piramuthu S,Tsai Y K.Job shop scheduling with a genetic algorithm and machine learning.Int J of Prod Res,1997,35(4):1171-1191
[20]陈荣兴,于明.混合型生产方式中动态调度问题的研究.工业工程与管理,2004,3:53-57
[21]高红,熊光愣.决策规则在仿真调度中的应用.控制与决策,1995,10(2):114-118
[22]陈伟达.基于杂合遗传算法的车间作业调度问题研究.南京:东南大学,2001
[23]王晓平,曹立明.遗传算法-理论、应用与软件实现.西安西安交通大学出版社,2002,1
[24]杨敬松.基于遗传算法的适应分布式生产模式车间计划调度的算法研究(硕).吉林长春理工大学计算机应用技术,2002
[25]De Jong K.A.An analysis of the behavior of genetic adaptive system:[Ph D Dissertation].Ann Arber:Univ.Microflims,1975
[26]王凌.车间调度及其遗传算法.北京:清华大学出版社,2003
[27]蔡自兴,徐光祜.人工智能及其应用.北京:清华大学出版社,2003
[28]张晴,饶运清.车间动态调度方法研究.质量·成本·管理,2003,41(461):39-41
[29]Szelde Elizabeth Kerr,Roger M.Knowledge-based reactive scheduling.Prod Plan & Contr,1994,5(5):124-145
[30]Nof S Y,Grant F H.Adaptive/predictive scheduling review and a general framework.Prod Plan & Contr,1991,2(4)..298-312
[31]Cott B J,Macchietto S.Minimizing the effects of batch process variability using on-line Schedule modification.Computers and Chemical Engineering,1989,13(1/2):105-113
[32]孙志峻.智能制造系统车间生产优化调度.南京:南京航空航天大学,2002
[33]Suresh V,Chandhuri D.Dynamic scheduling-Asurvey of research.Int J of Prod Econ,1993,32(1):53-63
[34]Kanet J J,Sridharan V.The electronic leistand,a new tool for shop scheduling.Manufacturing Review,1990,(3):161-170
[35]段新昱.虚拟现实基础与VRML程[M].北京:高等教育出版社,2004,3
[36]Shukla,C;Vazquez,M;Chen,F.F.Virtual manufacturing.,an overview[J].Computers &Industrial Engineering,Oct 1996,31(1/2),79-82
[37]Ward,J.Virtual manufacturing:really useful[J].Engineering,Jun 1998,239(6),48-52
[38]汪兴谦.VRML虚拟造型实战演练[M].中国水利水电出版社,2002.1
[39]ERKES J M,KENNY K B,LEWIS J W,SARACHAN B D,SOBOLEWSKIM W,SUM R N.Implementing shared manufacturing services on the world-wide Web[J].Communications of the ACM,February 1996,39(2)
[40]HOU Honglun,SUN Shouqian,PAN Yunhe.Cyber-design and Cyber-manufacturing,In:Proceedings of 3rd International Conference on CAID&CD,2000:400-405
[41]H V Kan,V G Duffy,C J Su.An Internet Virtual Reality Collaborative Environment for Effectvie Product Design[J].Computers in Industry,2001,45(2):197-213.
[42]刘战强,艾兴.虚拟制造技术及其应用的现状与发展展望[J].山东大学学报(工学版),2002,6,32(3):213-217
[43]Laus Peter Berier.Web- based Virtual Reality in Design and Manufacturing Applications.[EB/OL].http://www.vrl.umich.edu/berier/Papers/compit2000/WebB asedVR,htm,2001.
[44]晏文靖,王海艳,王汝传.基于VRML的网络虚拟制造技术的研究.2004.9,24(3):80-84
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |