摘要
流程工业是国民经济发展的重要支柱,并广泛存在于冶金、制药、化工等行业。用先进的制造、控制和管理技术对流程工业生产系统进行改造,保持关系国计民生的重点工业领域的又好又快发展,对于保障国家安全和增强国家经济竞争力都非常重要。生产调度是流程企业生产过程控制的核心,提高生产调度的质量和效率,实现资源的有效配置和生产设备的合理利用,是优化生产、节能降耗的有效途径,不仅符合经济效益的目标,也符合可持续发展的要求。节约能源是全人类的主题,是每个国家发展经济的一项长远的战略方针。流程工业是诸多工业领域中的能耗巨头,节能降耗是保证流程企业可持续发展的关键。
本文以国家自然科学基金重点项目《面向节能降耗的有色冶金过程控制若干理论与方法研究》(项目编号:60634020)的一个子项目:《流程工业过程的模式识别能耗寻优与优化调度方法研究》作为背景开展研究,以冶金工业中的动态调度问题为主要研究对象,主要做了以下工作:
1、针对经典调度问题中的混合流水车间调度问题(Hybrid Flow-shop Scheduling Problem, HFSP),引入空闲时间窗口机制,分别以最大流程时间最小和以能耗最小为主要目标的综合指标最小为目标,建立了数学规划模型。
2、采用粒子群算法(Particle Swarm Optimization, PSO)求解上述问题;为了克服基本PSO算法的缺陷,引入变异算子增强全局搜索能力,并使惯性权重随着进化代数的变化而变化以增强局部开发能力,构成混合PSO算法(Hybrid PSO, HPSO);仿真结果表明,HPSO算法的求解效果优于基本PSO算法。
3、针对实际生产过程中的实时任务和随机机器故障问题,提出了实时任务动态调度机制和处理机器故障的再调度机制,并采用HPSO算法进行仿真实验,结果表明了所提出的动态调度机制和算法求解动态调度问题的可行性、稳定性和最优性。
4、以铝工业生产系统为背景,将铝工业生产系统构成虚拟企业,并抽象为一个HFSP问题;按照本文介绍的理论与方法建立模型并求解动态调度问题,仿真实验说明了方法的可行性。
最后,对全文进行了总结,并对流程工业生产调度问题建模及其求解算法的下一步研究重点进行了展望。
Process industry is one of the pillar industries of national economy, and it is widespread in metallurgical industry, pharmaceutical industry, chemical industry and so on. Some industries of the key areas are of vital importance to the national economy and people’s livelihood. It is significant to keep these industries have good fast development for protecting national security and enhancing the national economic competitiveness by improving the process industry systems with advanced manufacturing, control and management theories and technologies. Production scheduling is the core of a process enterprise’s production process control. It is an effective way to improve the quality and efficiency of production scheduling and achieve the effective allocation of resources and rational use of production equipments for optimizing the production, saving energy and reducing consumption, which meets the economic demands and requirements of sustainable development. Saving energy is the theme of humanity and a long-term strategic policy for the economic development of each country. Process industry consumes a lot of energy, so saving energy and reducing consumption is a key to ensure the sustainable development of the process enterprises.
This paper has done some researches with the background of the project called the research on the methods of process industry’s pattern recognition, energy consumption optimization and scheduling, which is a part of the key national natural science fund project: the research on theories and methods of the non-ferrous metallurgical process control for energy saving and consumption reducing (Project number: 60634020).This paper researches on the dynamic scheduling problems in the metallurgical industry, and the mainly works are as follows:
1. Hybrid flow-shop scheduling problem (HFSP) is one of the typical scheduling problems. Introducing the mechanism of idle time window, this paper sets up the mathematical models of HFSP with the objective functions of minimizing the make-span and the composite indicator considering energy consumption respectively.
2. Particle swarm optimization algorithm (PSO) is employed to solve the HFSP. In order to overcome the shortcomings of basic PSO algorithm, hybrid PSO algorithm (HPSO) is structured by introducing the mutation operator to enhance the ability of global exploration and changing the inertia weight with the generation to enhance the ability of local exploitation. This paper has done some simulations which indicate that HPSO algorithm is superior to PSO algorithm in the solution of HFSP.
3. The dynamic scheduling mechanism facing real-time tasks and rescheduling mechanism facing machine breakdowns based on the mechanism of idle time window are proposed to deal with some uncertainties in the real production process. Then HPSO algorithm is employed to solving the dynamic scheduling problems, and the simulation results indicate that the mechanisms and the algorithms are feasible, stable and optimal in solving the dynamic scheduling problems.
4. With the background of the aluminum industry, this paper builds an aluminum production system as a virtual enterprise, and abstracts the scheduling problem of the virtual enterprise as HFSP. Then the mathematical model of this problem is set up and it is solved by the theories and methods introduced above, and the simulation indicates the feasibility of the theories and methods.
At last, the works of this paper are concluded and the prospective of future research on modeling and algorithm of process industry’s scheduling problem is discussed.
引文
[1]王万良,吴启迪.生产调度智能算法及其应用.北京:科学出版社. 2007.
[2] Michael, Pinedo. Scheduling:Theory,Algorithms,and Systems. Second Edition ed. New York: Pearson Education. 2002.
[3] Gass, S.I. Linear Programming Methods and Applications. Fifth Edition ed. MC: Graw Hill Book Company. 1990.
[4]国家发展和改革委员会.节能中长期专项规划.有色冶金节能. 2005. 22(2): p. 1-8.
[5]刘业翔,李劼.现代铝电解.北京:冶金工业出版社. 2008.
[6]王捷.氧化铝生产工艺.北京:冶金工业出版社. 2006.
[7]高阳,曾小青,周伟.多智能体协同生产管理及其系统.北京:清华大学出版社. 2006.
[8] Preiss, K., Goldman S.L., Nagel R. 21st Century Manufacturing Enterprises Strategy: An Industry-Led View. 1991: Iacocca Institute,Lehigh University.
[9] Tulluri, S.,Baker R.C. A Quantitative Framework for Designing Efficient Business Process Alliances. Proceedings of the 1996 International Conference on Engineering Management and Control. 1996: p. 656-660.
[10] Grainer, R.,Metes G. Has Out Sourcing Gone Too Far. Business Week. 1996. 4(1): p. 28.
[11] Walton, J.,Whicker L. Virtual Enterprise:Myth and Reality. Journal of Control. 1996. 27(3): p. 22-25.
[12] Salvador, M. S. A Solution of Special Class of Flow Shop Scheduling and Its Application. Berlin: Springer-Verlag. 1973.
[13] Junlin, Chang, Weiwu Yan, Huihe Shao. Scheduling a two-stage no-wait hybrid flowshop with separated setup and removal times. Proceedings of the 2004 American Control Conference. 2004: p. 1412-1416.
[14] Hentous, H.,Benhammadi F. Heuristics Resolution of a Constrained Hybrid Flow Shop Problem. Proceedings of the 11th IEEE Symposium on Computers and Communications. 2006: p. 62-63.
[15] Roberto, Macchiaroli. Modelling Flexible Flow Lines with Generalized Stochastic Petri Nets. Porceeding of the 4th International Conference on Computer Integrated Mamufacturing and Automation Technology. 1994: p. 411-416.
[16] T.C. Edwin Cheng,G.Q. Wang. A Note on Scheduling Two-machine Flexible Flowshop. IEEE Transactions on Robotics and Automation. 1999. 15(1): p. 187-190.
[17] Li, Wang,Dawei Li. A scheduling algorithm for flexible flow shop problem. Proceedings of IEEE World Congress on Intelligent Control and Automation. 2001: p. 3106-3108.
[18] Wendong, Xiao, Peifeng Hao, Sen Zhang, et al. Hybrid Flow Shop Scheduling Using Genetic Algorithms. Proceeding of the 3rd World Congress on Intelligent Control and Automation. 2000: p. 537-541.
[19]邱竹贤.预焙槽炼铝.北京:冶金工业出版社. 2005.
[20]王捷.电解铝生产工艺与设备.北京:冶金工业出版社. 2006.
[21]钱晓龙,唐立新,刘文新.动态调度的研究方法综述.控制与决策. 2001. 16(2):p. 141-145.
[22] In, Lee, Riyaz Sikora, Michael J.Shaw. A Genetic Algorithm-basic Approach to Flexible Flow-line Scheduling with Variable Lot Sizes. IEEE Transactions on System, Man and Cybernetics(Part:B). 1997. 27(1): p. 36-54.
[23] Junlin, Chang, Guangfu Ma, Xiaoping Ma. A New Heuristic for Minimal Makespan in No-Wait Hybrid Flowshops. Proceedings of the 25th Chinese Control Conference. 2006: p. 1352-1356.
[24] Yi, Wu, Min Liu, Cheng Wu. A Genetic Algorithm for Solving Flow Shop Scheduling Problems with Parallel Machine and Special Procedure Constraints. Proceedings of the 2th MLC conference. 2003: p. 1774-1779.
[25]崔建双,李铁克,张文新.混合流水车间调度模型及其遗传算法.北京科技大学学报. 2005. 27(5): p. 623-626.
[26]谷峰,陈华平,卢冰原, et al.粒子群算法在柔性作业车间调度中的应用.系统工程. 2005. 23(9): p. 22-23.
[27]潘全科,朱剑英.作业车间动态调度研究.南京航空航天大学学报. 2005. 37(2): p. 262-268.
[28] Jackson, J.R. Simulation Research on Job Shop Production. Naval Research Logistic Quart. 1957. 4(3): p. 287-295.
[29] Ishii, N,M Muraki. A Process-Variability-Based Online Scheduling System In Multi-Product Batch Plants. Computers and Chemical Engineering. 1996. 20(2): p. 217-234.
[30]方剑,席裕庚.周期性和事件驱动的Job-Shop滚动调度策略.控制与决策. 1997. 12(2): p. 159-162.
[31]刘琳,谷寒雨,席裕庚.工件到达时间未知的动态车间滚动重调度.机械工程学报. 2008. 44(5): p. 68-75.
[32] Hamidzadeb, B. Dynamic scheduling of real-time tasks, by assignment. IEEE Concurrency [see also IEEE Parallel & Distributed Technology]. 1998. 6: p. 14-25.
[33] Alaide, D., A. Rodriguez-Gonzalez, A. Sicilia. An approach to solve t he minimum expected makespan flow-shop problem subject to breakdowns. European Journal of Operation Research. 2002. 140(2): p. 384-398.
[34] Xiaoqiang, Cai, Xianyi Wu, Xian Zhou. Dynamically Optimal Policies for Stochastic Scheduling Subject to Preemptive-Repeat Machine Breakdowns. IEEE Transactions on Automation Science and Engineering. 2005. 2(2): p. 158-172.
[35] Wen-Jun, Yin, Liu Min, Wu Cheng. Learnling Single-Machine Scheduling Heuristics Subject to Machine Breakdowns with Genetic Programming. Proceedings of IEEE International Conference on Intelligent Control and Automation. 2003: p. 105.-1055.
[36]刘昶,史海波,袁杰.具有随机机器故障的制造过程建模与性能分析.计算机集成制造系统. 2008. 14(9): p. 1704-1709,1716.
[37] Chin-Soon, Chong, AppaIyer Sivakumar, Robert Gay. Simulation-based scheduling for dynamic discrete manufacturing. Proceedings of the 2003 Winter Simulation Conference. 2003: p. 1465-1473.
[38] Mikkel, T.Jensen. Generating Robust and Flexible Job Shop Schedules Using Genetic Algorithms. IEEE Transactions on Evolutionary Computation. 2003. 7(3): p. 275-288.
[39] Gyula, Kulcsár,Ferenc Erdélyi. A New Approach to Solve Multi-Objective Scheduling and Rescheduling Tasks. International Journal of ComputationalIntelligence Research. 2007. 3(4): p. 343-351.
[40]李素粉,朱云龙,尹朝万.具有随机加工时间和机器故障的流水车间调度.计算机集成制造系统. 2005. 11(10): p. 1425-1429.
[41] Dong, Chen, Feng Liu, Peter B. Luh. Scheduling Job Shops with Uncertainties. Proceeding of the 36th Conference on Decision and Control. San Diego,California USA. 1997: p. 3556-3561.
[42] Sawat, Pararach, Pichit Sukcharoenpong, Peerayuth Charnsethikul. An Improvement of the Lower Bound in FlowshopS chedulingw ith Uncertain ProcessinTg imes. Thammasat International Journal of Science and Technology. 2006. 11(4): p. 27-36.
[43] Sotskov, Y.N ., Allahverdi A., Lai T-C. Flowshop scheduling problem to minimize total completion time with random and bounded processing times Journal of the Operational Research Society. 2004(55): p. 277-286.
[44]冯欣,唐立新,王梦光. BAB算法中集成CPT求解job-shop调度问题.管理科学学报. 2005. 8(3): p. 81-89.
[45]轩华,唐立新.带多处理器任务的动态混合流水车间调度问题.计算机集成制造系统. 2007. 13(11): p. 2254-2260.
[46]陶泽,肖田元,赵志军.基于Petri网和GASA的JSP动态分类调度研究.系统仿真学报. 2008. 20(22): p. 6238-6241,6247.
[47]舒海生,李庆芬,颜声远, et al. FMS动态调度仿真模型的研究.哈尔滨工程大学学报. 2005. 26(2): p. 192-196.
[48] Shen, Wei Ming, Wang Lihui, Hao Qi. Agent-Based Distributed Manufacturing Process Planning and Scheduling:A State-of-the-Art Survey. IEEE Transactions on Systems, Man and Cybernetics(Part C). 2006. 36(4): p. 563-577.
[49] Wang, Hanlun,Wang Yadong. Multi-Agent System Negotiation Based on Expanded Contract Net Protocol Research Proceedings of IEEE NLP-KE. 2005: p. 472-478.
[50] Ramos, Carlos. An architecture and a negotiation protocol for the dynamic scheduling of manufacturing systems. Proceedings of 1994 IEEE International Conference on Robotics and Automation. 1994: p. 3161-3166.
[51] Ramos, Carlos. Task negotiation for distributed manufacturing systems. Proceedings of IEEE International Symposium on Assembly Task Planning. 1995: p. 259-264.
[52]李飒,王云莉,段广洪, et al.基于多智能体结构的车间动态调度方法.机械科学与技术. 2000. 19(6): p. 956-958.
[53]吕赐兴,朱云龙,尹朝万.基于Agent的生产调度混合协商策略研究.计算机集成制造系统. 2006. 12(12): p. 2074-2081.
[54]王纯贤,王治森,董伯麟, et al.基于Agent反、正向招标技术的Job Shop调度研究.组合机床与自动化加工技术. 2006(5): p. 90-03.
[55] Armando, Walter Colombo, Ronald Schoop, Ralf Neubert. An Agent-Based Intelligent Control Platform for Industrial Holonic Manufacturing Systems. IEEE Transaction on Industrial Electronics. 2006. 53(1): p. 322-337.
[56]张晴,饶运清.车间动态调度方法研究.机械制造. 2003. 41(1): p. 39-41.
[57]孙志峻,朱剑英,潘全科.基于遗传算法的多资源作业车间智能动态优化调度.机械工程学报. 2002. 38(4): p. 120-125.
[58]柴永生,孙树栋,余建军, et al.基于免疫遗传算法的车间动态调度.机械工程学报. 2005. 41(10): p. 23-27.
[59] Yanhong, Wang, Lixin Yan, Hongyu Zhu, et al. A Genetic Algorithm for Solving Dynamic Scheduling Problems in Distributed Manufacturing Systems. Proceedings of the 6th World Congress on Intelligent Control and Automation. 2006: p. 7343-7347.
[60]鞠全勇,朱剑英.基于混合遗传算法的动态车间调度系统的研究.中国机械工程. 2007. 18(1): p. 40-43.
[61] Buthainah F, Al-Dulaimi,Hanza A.Ali. A Novel Genetic Algorithm Approach for Solving Flow Shop Problem. International Journal of Computer Science and Network Security. 2008. 8(9): p. 229-235.
[62] Hela, Boukef, Mohamed Benrejeb, Pierre Borne. A Proposed Genetic Algorithm Coding for Flow-Shop Scheduling Problems. International Journal of Computers, Communications & Control. 2007. 2(3): p. 229-240.
[63]王万良,唐宇.微粒群算法的研究现状与展望.浙江工业大学学报. 2007. 35(2): p. 136-141.
[64]郜庆路,罗欣,杨叔子.基于蚂蚁算法的混流车间动态调度研究.计算机集成制造系统. 2003. 9(6): p. 456-459,475.
[65]王延斌,王刚,赵立忠, et al.基于蚁群算法的模具制造动态调度研究.计算机集成制造系统. 2006. 12(7): p. 1028-1036.
[66]马慧民,柳毅,叶春明.基于改进粒子群算法求解单级多资源约束生产批量计划问题.工业工程与管理. 2005(6): p. 66-70.
[67]沈兵虎,柳毅,潘瑞芳.改进微粒群算法求解模糊交货期Flow-shop调度问题.计算机工程与应用. 2006(34): p. 36-38.
[68] Fabrice, Chauvet, Jean-Marie Proth, Yorai Wardi. Scheduling No-Wait Production with Time Windows and Flexible Processing Times. IEEE Transactions on Robotics and Automation. 2001. 17(1): p. 60-68.
[69]刘向,邹逢兴,张湘平, et al.面向节能的混合流水车间调度方法的研究. The 27th Chinese Control Conference. 2008: p. 48-53.
[70]施光燕,董加礼.最优化方法.北京:高等教育出版社. 2006.
[71]戴文战.一种动态多目标决策模型及其应用.控制与决策. 2000. 15(2): p. 197-200.
[72]唐五湘,陈一青.确定经济规模的相关分析---多指标综合评价法及其应用.系统工程理论与实践. 1996. 16(4): p. 52-59.
[73]卢跃林,施放.多目标决策中目标转换得效用函数法.自动化理论、技术与应用. 1997(4): p. 651-654.
[74]蔡力钢,张建设,张正义, et al.复杂零件工艺方案全局多层并行优化.机械工程学报. 2008. 44(9): p. 6-12.
[75] T.C. Edwin, Cheng,Guoqing Wang. A Note on Scheduling Two-machine Flexible Flowshop. IEEE Transactions on Robotics and Automation. 1999. 15(1): p. 187-190.
[76]李建祥,唐立新,吴会江.具有提前/拖期惩罚的热轧钢管批调度问题研究.控制与决策. 2005. 20(6): p. 665-668,678.
[77]卢冰原,古春生,谷峰.基于粒子群优化的模糊交货期惩罚问题的研究.计算机工程与应用. 2006. 42(19): p. 8-10,16.
[78]李岩,吴智铭.基于两级遗传算法的模糊化计划调度.上海交通大学学报. 1999.33(11): p. 1337-1340.
[79]双兵,顾幸生.面向定单交货期窗的连续生产过程生产调度.中南工业大学学报. 2003. 34(4): p. 420-423.
[80] Liu, Xiang, Zou Fengxing, Zhang Xiangping. Mathematical Model and Genetic Optimization for Hybrid Flow Shop Scheduling Problem Based on Energy Consumption. 2008 Chinese Control and Desicion Conference. Yantai,China. 2008.
[81]欧微,邹逢兴,高政.基于混合粒子群算法的柔性Flow-shop调度方法研究. 2008 Chinese Control and Decision Conference. 2008: p. 946-951.
[82] Kenney, J.,Eberhart R. Particle swarm optimization. Proceedings of the 6th International Symposium on Micro Machine and Human Science. 1995: p. 1942-1948.
[83] Kenney, J.,Eberhart R. A new optimizer using particle swarm theory. Proceedings of the 6th Int Symposium on Micro Machine and Human Science. 1995: p. 39-43.
[84]谢晓峰,张文俊,杨之廉.微粒群算法综述.控制与决策. 2003. 18(2): p. 129-134.
[85] Hao, T. A. N., L. I. Yufeng, Wang Jinyan. AC-PSO algorithm for NUV mission planning. Transactions of Nanjinn universily of Aeronautics & AstronauLics. 2005. 22(3): p. 264-271.
[86]赵先章,常红星,曾隽芳, et al.一种基于粒子群算法的移动机器人路径规划方法.计算机应用研究. 2007. 24(3): p. 181-186.
[87]需秀娟,史忠科.粒子群优化算法在多目标优化中的应用与仿真.计算机工程与应用. 2006. 42(2): p. 28-29,181.
[88]庞巍,上康平,周春光.模糊离散粒子群优化算法求解旅行商问题.小型微型计算机系统. 2005. 26(8): p. 1331-1334.
[89] Zhixiong, Liu,Shaomei Wang. Hybrid Particle Swarm Optimization for Permutation Flow Shop Scheduling. Proceeding of the 6th World Congress on Intelligent Control and Automation. 2006: p. 3245-3249.
[90]周强.考虑随机加工时间和机器故障的多目标流水车间调度.计算机时代. 2008(6): p. 9-10,18.
[91]宋本基,喻宏斌,郑鹏, et al. FMS故障调度问题的研究及仿真.哈尔滨工程大学学报. 2000. 21(4): p. 56-59.
[92]尹文君,刘民,吴澄.随机故障下单机鲁棒调度算法的遗传编程方法.清华大学学报(自然科学版). 2005. 45(1): p. 81-84.
[93]陶泽,肖田元,郝长中.基于Petri网的JSP动态分类调度.计算机工程与应用. 2007. 43(20): p. 240-244,248.
