摘要
在现代制造模式中多品种、小批量生产愈来愈多，对产品成本和质量的要求越来越高，因此对车间运作管理也提出了标准化、精细化的要求，致使管理者愈发关注生产中存在的不确定性及其对生产的影响。在实际工作中信息的获得具有不及时和不完整的特点。生产调度需及时了解、充分考虑这些影响因素，在调度方案制定前需防范此因素对生产造成的不平衡隐患，在执行过程中调度方案需随时动态调整以适应这些变化。在总结以往工作的基础上，本文研究混装和作业车间调度时处理不确定的框架、机制和措施，提出在不确定条件下的鲁棒调度方法和动态自适应反应式策略，并对生产过程中的不确定信息处理和参数校正方法进行探讨。本文的主要工作如下：
以系统性消除不确定因素的影响为目标，构造了结合预防式调度、反应式调度与不确定推理于一体的整体调度框架。以具有不确定吸收能力的鲁棒调度方案作为生产开始前的预调度方案，基于调度结果通过贝叶斯推理对预估的不确定参数分布进行再处理和修正；利用具有不确定反馈能力的反应式调度，应对生产中各种突发事件，评估并修正应对策略，为下一阶段的预防式和反应式调度提供更可靠的决策依据。
基于预防式调度思想，研究具有不确定吸收能力的鲁棒调度方法。针对具有不确定操作时间的混合装配线平衡问题，基于混合整型线性规划建立相应的鲁棒对等模型；针对具有不确定操作时间的作业车间调度问题，建立基于调度目标期望值的目标规划模型并开发相应的智能算法对模型进行求解。
针对生产过程中出现的设备故障、订单改变等突发事件，通过调整系统参数中的设备和工件等，提出具有自适应能力的反应式调度方法。并针对柔性作业车间调度问题，开发具有双层编码的遗传算法。
研究不确定信息的处理及不确定参数的校正方法。以随机变量的上界、下界、均值和方差为不确定参数描述手段，建立基于随机变量的鲁棒解与基于均值的确定解之间的对应关系。以贝叶斯网络为工具，结合后验信息与先验统计进行分布参数的校正处理，以获得更符合实际情况的分布参数。
为降低调度问题的计算复杂性，研究两种快速算法——针对装配线平衡问题的摹加代数方法和针对作业车间调度的Hopfield-神经网络算法。对于前者，通过数学命题证明在摹加代数意义上，简单装配线平衡问题可等价于旅行商问题；对于后者，基于Lyapunov稳定性理论证明方法的收敛性。并通过实际算例验证两种方法的有效性。
In the modern manufacturing mode, there are more and more variety and small batchesproduction,lower cost and higher quality,so standardization and fine are put forward formanufacturing workshop operation management, which cause that managers increasingly focuson existed uncertainty in the production and its impact on the production.The information thatget in the practical work is not timely or incomplete.Because science and technology and marketchange quickly,in order to respond to these challenges,it put forward a higher and morestringent requirements for Workshop’s uncertain scheduling method and technology.Productionscheduling need understand it in a timely manner and taking into full account these factorsfully,this will prevent and eliminate the imbalanced danger in production,the scheduling schemein the execution process needs to dynamically adjust to these changes at any time.
Based on the summaries of the past work,this parer puts forward the frame and mechanismfor uncertain dynamic scheduling, analyzes the impact on production process cased by uncertaininformation, proposes robust scheduling method and dynamical adaptive reactive strategy underuncertainty and explores the uncertain information processing and parameter correction methodin the production process.
The main work and research results are shown as follows:
This paper analyzes dynamic scheduling mechanism under uncertain environment, comesup with the overall scheduling framework combined with the scheduling of proactive andreactive scheduling, set robust scheduling with uncertain absorption capacity as thepre-scheduling scheme before start of the production, take the strategy combined withevent-driven strategy and the receding horizon in production, develop the adaptive responsescheduling algorithm in response to emergencies, and use Bayesian filtering algorithm toreprocess and correct uncertain information to provide a more reliable basis for decision makingfor pre-scheduling in the next phase.
Concerning assembly line balancing problem and more universal job shop schedulingproblems,this paper analyzes the robust scheduling method that has uncertain absorption capacity.For the assembly line balancing problem, this paper establishes a robust integer linearprogramming model that can cope with the problems with uncertain operation time parameters.this paper establishes goal programming model based scheduling target expectations and developthe intelligent algorithm for job shop scheduling problem to solve the problem.
Concerning the emergencies and disturbances in the production process, this paperinvestigate reactive scheduling method. This paper develop adaptive double-coded geneticalgorithm for flexible job shop scheduling problem.
According to the universal computational complexity for the scheduling problem,this paper develops two fast algorithms-G plus algebraic method for assembly line scheduling problem and hopfield neural network algorithm for job shop scheduling problem.For the former,the assembly line balancing problem is equivalent to the traveling salesman problem proved bymathematical proposition in the sense of G plus algebraic. For the latter, Convergence of themethod is proved based on Lyapunov stability theory. And the effectiveness of the two methodsis verified.
This part researches on processing method for uncertain information and the correctionmethods for the uncertain parameters.Concerning the uncertain parameters in the productionoperating system, this paper set Bayesian theory as a tool, use production data in the posterior tocorrect Prior statistical distribution parameters in order to obtain a more realistic distribution ofthe parameters and provide a reliable guarantee for accuracy and precision in the followingproduction process.
引文
[1] Paul M. Swamidass. Innovations in competitive manufacturing[M]. Holland: Kluwer AcademicPublishers,2000:145-154.
[2] Xiu-Tian Yan, Cheng-Yu Jiang, Neal P. Juster. Perspectives from Europe and Asia on EngineeringDesign and Manufacture: A Comparison of Engineering Design and Manufacture in Europe and Asia[M].Holland: Kluwer Academic Publishers,2004:297-305.
[3]陈国权.企业实施敏捷制造的过程框架[J],清华大学学报,1999,14(2):56-59.
[4]赵勇,查建中.敏捷制造研究新进展及应用前景[J],高技术通讯,2002,10:107-110.
[5] Li X., Gao L., Zhang C., etc. A review on integrated process planning and scheduling[J]. Int J Manuf Res,2010,5:161–180.
[6] Baker K. R., Trietsch D. Principles of sequencing and scheduling[M]. New York: Wiley,2009.
[7] Xhafa, F., Abraham, A. Studies in computational intelligence: Vol.128. Metaheuristics for scheduling inindustrial and manufacturing applications[M]. Berlin: Springer,2008.
[8]李琳.混合生产型企业的生产调度优化研究[M],上海:上海交通大学出版社,2011,3-9.
[9] Tien-Fu Liang. Integrated manufacturing/distribution planning decisions with multiple imprecise goals inan uncertain environment[J]. Quality&Quantity,2012,46(1):137-153.
[10] You-lun Xiong, Zhou-ping Yin. Digital manufacturing—the development direction of the manufacturingtechnology in the21st century[J]. Frontiers of Mechanical Engineering in China,2006,1(2):125-130.
[11] John A. Buzacott, Marvin Mandelbaum. Flexibility in manufacturing and services: achievements, insightsand challenges[J]. Flexible Services and Manufacturing Journal,2008,20(1):13-58.
[12] Vahidreza Ghezavati, Mohammad Saidi-Mehrabad. Designing integrated cellular manufacturing systemswith scheduling considering stochastic processing time[J]. The International Journal of AdvancedManufacturing Technology,2010,48(5):707-717.
[13] Su-Hyun Jung, Sung-Hong Kim, Sung-Lyong Kang. A the Effects of SCM Activities on ManufacturingCapabilities and Manufacturing Performances[J]. Communications in Computer and Information Science,2011,264:306-315.
[14] Juergen Ackermann. Robustness of Dynamic Systems with Parameter Uncertainties[M]. Monte Verità1992:291-302.
[15] Zukui Li, Marianthi Ierapetritou. Process scheduling under uncertainty: Review andchallenges.Computers and Chemical Engineering,2008,32:715-727.
[16] M. Pinedo. Scheduling-Theory, Algorithms, and Systems, Third Edition[M]. Springer,2008.
[17]唐国春,现代排序论[M].上海:上海科学普及出版社,2003.
[18] Marianne Akian, Jean-Pierre Quadrat, Michel Viot. Bellman processes[C].11th International Conferenceon Analysis and Optimization of Systems Discrete Event Systems,1994,199:302-311.
[19] Maccarthy BL, Liu J.. Addressing the gap in scheduling research-a review of optimization and heuristicmethods in production scheduling. Int J Prod Res,1993,31(1):59–79.
[20] S.M. Johnson. Optimal two-and three-stage production schedules with setup times included. Naval Res.Logist. Quart.1954,1:61–68.
[21] Liu, M., Hao, J., Wu, C. A prediction based iterative decomposition algorithm for scheduling large-scalejob shops[J]. Mathematical and Computer Modelling,2008,47:411–421.
[22] Gao, J., Sun, L., Gen, M. A hybrid genetic and variable neighborhood descent algorithm for flexible jobshop scheduling problems[J]. Computers&Operations Research,2008,35:2892–2907.
[23] Lin, T.L., Horng, S.J., Kao, T.W., etc. An efficient job-shop scheduling algorithm based on particleswarm optimization[J]. Expert Systems with Applications,2009,37:2629–2636.
[24] Kimbrel, T., Sviridenko, M. High-multiplicity cyclic job shop scheduling[J]. Operations Research Letters2008,36:574–578.
[25] Yang, J., Sun, L., Lee, H.P., etc. Clonal Selection Based Memetic Algorithm for Job Shop SchedulingProblems[J]. Journal of Bionic Engineering2008,5:111–119.
[26] Oliveira, J.A., Dias, L., Pereira, G. Solving the Job Shop Problem with a random keys genetic algorithmwith instance parameters[C]. Proceedings of2nd International Conference on Engineering Optimization,CDRom, Lisbon, Portugal,2010.
[27] Li, Y., Chen, Y. A Genetic Algorithm for Job-Shop Scheduling[J]. Journal of Software,2010,5(3):269–275.
[28] Ruiz R., Vázquez-Rodríguez J. A. The hybrid flow shop scheduling problem[J]. Eur J Oper Res,2010,205:1–18.
[29] Huang Y. M., Shiau D. F. Combined column generation and constructive heuristic for a proportionateflexible flow shop scheduling[J]. Int J Adv Manuf Technol,2008,38(7/8):691–704.
[30] Guo Y. W., Li W. D., Mileham A. R., etc. Applications of particle swarm optimisation in integratedprocess planning and scheduling[J]. Robot Comput-Integr Manuf,2009,25:280–288.
[31] Zhao F., Hong Y., Yu D., etc. A hybrid particle swarm optimisation algorithm and fuzzy logic for processplanning and production scheduling integration in holonic manufacturing systems[J]. Int J Comput IntegrManuf,2010,23:20–39.
[32] Xingquan Zuo, Xingquan Zuo, Huiping Lin, etc. Workflow Simulation Scheduling Model withApplication to a Prototype System of Cigarette Factory Scheduling[J]. Systems Modeling and Simulation,2007:158-162.
[33]于兆勤.混合型装配线平衡问题的不确定性仿真研究[J],中国机械工程,2008,11,1297-1302.
[34]张国泽,冯毅萍,荣冈.不确定条件下基于仿真的流程工业调度方案优化[J].计算机与应用化学,2011,28(7):933-938.
[35] Koulamas C., Kyparisis G. J. A note on the proportionate flow shop with a bottleneck machine[J]. Eur JOper Res,2009,193:644–645.
[36] Li X., Gao L., Zhang C., etc. A review on integrated process planning and scheduling[J]. Int J Manuf Res,2010,5:161–180.
[37] Li X., Gao L., Shao X., etc. Mathematical modeling and evolutionary algorithm-based approach forintegrated process planning and scheduling[J]. Comput Oper Res,2010,37:656–667.
[38] Baykasoglu A., zbak r L. A grammatical optimization approach for integrated process planning andscheduling[J]. J Intell Manuf,2009,20:211–221.
[39] zgüven C., zbak r L., Yavuz Y. Mathematical models for job shop scheduling problems with routingand process plan flexibility[J]. Appl Math Model,2010,34:1539–1548.
[40] Baker K. R., Trietsch D. Principles of sequencing and scheduling[M]. New York: Wiley,2009.
[41] Janak, S. L.; Lin, X.; Christodoulos A. Floudas. A New Robust Optimization Approach for Schedulingunder Uncertainty: II. Uncertainty with Known Probability Distribution. Computers and ChemicalEngineering2007,31,171-195.
[42] Stacy L. Janak; Christodoulos A. Floudas. Production scheduling of a large-Scale industrial batch plant. II.Reactive scheduling. Computers&Chemical Engineering,2006,45(25):8253-8269.
[43] Mahdavi I., Shirazi B., Solimanpur M. Development of a simulation-based decision support system forcontrolling stochastic flexible job shop manufacturing systems[J]. Simul Model Pract Theory,2010,18:768–786.
[44] ChungCheng Lu, ShihWei Lin, KuoChing Ying, Robust scheduling on a single machine to minimize totalflow time, Computers&Operations Research,2012.39(7):1682-1691.
[45]杨宏兵,严洪森,陈琳,知识化制造环境下模糊调度模型和算法.计算机集成制造系统.2009.15(7):1374-1382.
[46] Chung-Cheng Lu, Shih-Wei Lin, Kuo-Ching Ying. Robust scheduling on a single machine to minimizetotal flow time[J]. Computers&Operations Research,2012,(39)7:1682-1691.
[47] Leon V J, wu S D, Storer R H. Robustness measures and robust scheduling for job-shop[J]. IEEETransactions，1994,26(5):32~43.
[48] Abumaizar R J, Svestka J A. Rescheduling job shops under random disruptions[J]. International JournalofProduction Research,1997,35(7):2065-2082.
[49] ChungCheng Lu, ShihWei Lin, KuoChing Ying, Robust scheduling on a single machine to minimize totalflow time, Computers&Operations Research,2012.39(7):1682-1691.
[50] Matias Holte, Carlo Mannino.The implementor/adversary algorithm for the cyclic and robust schedulingproblem in health-care. European Journal of Operational Research,2013.226(3):551-559.
[51] Xiaole Han, Zhiqiang Lu, Lifeng Xi. A proactive approach for simultaneous berth and quay cranescheduling problem with stochastic arrival and handling time. European Journal of Operational Research,2010.207:1327-1340.
[52] A. Bonfill, A. Espu na, L. Puigjaner. Proactive approach to address the uncertainty in short-termscheduling. Computers and Chemical Engineering,2008.32:1689-1706.
[53] Xu Weida, Xiao Tianyuan. Strategic Robust Mixed Model Assembly Line Balancing Based on ScenarioPlanning. TsingHua Science and Technology.2011,16(3):308-314.
[54] Zhiqiang Cai, Shudong Sun, Shubin Si, Bernard Yannou. Identifying product failure rate based on aconditional Bayesian network classifier. Expert Systems with Applications,2011,38(5):5036-5043.
[55] Juan M. Novas, Gabriela P. Henning. Reactive scheduling framework based on domain knowledge andconstraint programming. Computers&Chemical Engineering,2010,34(12):2129-2148.
[56] Filip Deblaere, Erik Demeulemeester, Willy Herroelen. Reactive scheduling in the multi-modeRCPSP.Computers&Operations Research,2011,38(1):63-74.
[57]刘琳，谷寒雨，席裕庚.工件到达时间未知的动态车间滚动重调度.机械工程学报,2008,44(5):68-75.
[58] Lin Lin, Mitsuo Gen, Yan Liang, Katsuhisa Ohno. A Hybrid EA for Reactive Flexible Job-shopScheduling. Procedia Computer Science,2012.12:110-115.
[59] Li Nie, Liang Gao, Peigen Li, Xinyu Li. A GEP-based reactive scheduling policies constructing approachfor dynamic flexible job shop scheduling problem with job release dates. Journal of IntellectualManufacturing, DOI10.1007/s10845-012-0626-9.2012. Online.
[60] Kari Stuart, Erhan Kozan. Reactive scheduling model for the operating theatre. Flexible Services andManufacturing Journal,2012.24:400-421.
[61] Jing Yin, Tieke Li, Baojiang Chen, Bailin Wang. Dynamic Rescheduling Expert System for Hybrid FlowShop with Random Disturbance. Procedia Engineering,2011,15:3921-3925.
[62] Bulbul, K. A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardinessproblem[J]. Omputers&Operations Research,2011,38(6):967–983.
[63] Sugimura N, Tanimizu Y, Iwamura K,(2004) A study on real-time scheduling for holonic manufacturingsystem. CIRP journal of manufacturing systems,33,5:467-475.
[64]孙林,孙志刚,李飞.母线生产制造中的鲁棒性调度研究[J].黑龙江科技信息,2011(24):27-28.
[65] Feiza Ghezail, Henri Pierreval, Sonia Hajri-Gabouj. Analysis of robustness in proactive scheduling: Agraphical approach. Computers&Industrial Engineering,2010,58:193-198.
[66] Zukui Li, Marianthi Ierapetritou. Process scheduling under uncertainty: Review andchallenges.Computers and Chemical Engineering,2008,32:715-727.
[67] Moratori, P. B., Petrovic, S.,&Vázquez, A.. Match-up strategies for job shop rescheduling. InternationalConference on Industrial, Engineering&Other Applications of Applied Intelligent Systems (IEA/AIE),2008:119-128.
[68] Olivier Lambrechts, Erik Demeulemeester, Willy Herroelen. Proactive and reactive strategies forresource-constrained project scheduling with uncertain resource availabilities. Journal of Scheduling.2008,11:121-136.
[69]陈宇，陈新，陈新度，张平.基于设备整体效能和多Agent的预测-反应式调度[J].计算机集成制造系统，2009,15(8):1599-1605,1613.
[70]刘琳,谷寒雨,席裕庚.工件到达时间未知的动态车间滚动重调度[J].机械工程学报,2008,44(5):68-75
[71]刘明周,单晖,蒋增强等.不确定条件下车间动态重调度优化方法[J].机械工程学报,2009,45(10):137-142.
[72]李聪波,刘飞,易茜.基于关键链的再制造系统不确定性生产调度方法[J].机械工程学报,2011,47(15):121-126.
[73] Tanimizu Y, Sugimura N,(2002) A study on reactive scheduling based on genetic algorithm. Proc. of the35th CIRP international seminar on manufacturing systems:219-224.
[74] Wu S D, Storer R H, Chang P C. One-machine rescheduling heuristics with efficiency and stability ascriteria[J]. Computers and Operations Research,1993,20(1):1-14.
[75] Sabuncuoglu I, Karabuk S. Rescheduling frequency in an FMS with uncertain processing times andunreliable machines[J]. Journal of Manufacturing Systems,1999,18(4):268-283.
[76] Wh H H, Li. R K. A new rescheduling method for computer based scheduling systems[J]. InternationalJournal of Production Research,1995,33(8):2097-2110.
[77] Leon VJ, Wu S D, Storer RH. Games theoretic control approach for job shops in the presence ofdisruptions[J]. International Journal of Production Research,1994,32(6):1451-1476.
[78] Abumaizar R J, Svestka J A. Rescheduling job shops under disruptions[J]. International Journal ofProduction Research,1997,35(7):2065-2082.
[79]羌磊,肖田元,宋士吉.基于不确定作业时间的FSMP调度问题研究[J].控制与决策,2004,2:162-165,170.
[80] Zhang C. Y., Gao L., Shi Y. An effective genetic algorithm for the flexible job-shop schedulingproblem[J]. Exp Syst Appl,2011,38(4):3563–3573.
[81]李平,夏绪辉,唐秋华.基于摹加代数优化的装配线平衡方法[J].武汉科技大学学报(自然科学版),2011,34(3):228-232.
[82] Gutjahr A L, Nemhauser G L. An algorithm for the line balancing problem. ManagementScience,1964,11
[83]肖中华基于改进遗传算法的汽车装配线平衡问题研究[D]武汉科技大学
[84]杜运普,杨月新装配线生产线的平衡问题研究[J]机械设计与制造,2003,2
[85] Ponnambalam S G.Aravindan P.Rao P S. Com-parative evaluation of genetic algorithms for job-shopscheduling[J]. Production Planning&Control,2001
[86]秦裕瑗离散动态规划与bellman代数[M]2009.1北京：科学出版社
[87]秦裕瑗最优路问题——极优代数方法[M]2009.9上海：上海科学技术出版社
[88]郑大钟,赵千川离散事件动态系统[M]2001北京：清华大学出版社
[89]陈进,吕新峰,王滨滨等基于极大极小代数法的最优调度方法[J]机械制造,2005,11
[90]李妍峰,李军,赵达.用动态搜索算法求解时间依赖型旅行商问题[J].西南交通大学学报,43(2008)
[91] P. Bratley, B.L. Fox, L.E. Schrage. A guide to Simulation[M]. New-York: Springer Verlag,1983.
[92]罗亚波.作业系统调度优化理论与方法[M].武汉:华中科技大学出版社,2011.
[93] Foo S. Y-P, Takefuji Y. Stochastic neural networks for solving job-shop scheduling: Parts Ⅰ. Problemrepresentation. In: Proceeding of the IEEE International Conference on Neural Networks: Vol. Ⅱ, SanDiego, CA.1988.275-282.
[94] Foo S. Y-P, Takefuji Y. Stochastic neural networks for solving job-shop scheduling: Parts Ⅱ.Architecture and simulations. In: Proceeding of the IEEE International Conference on Neural Networks:Vol. Ⅱ, San Diego, CA.1988.283-290.