摘要
随着科学技术的高速发展和全球竞争的日益加剧,制造业企业间的竞争也越演越烈。为了不断提高并保持在市场竞争中的优势地位,保持核心竞争力,企业必须加强内部的生产管理,特别是生产管理的核心——车间调度管理。车间调度作为整个企业的支柱和核心,它是企业物料流、控制流和信息流的交汇点,也是实现整个公司运营目标的基础和根本所在。有效的调度方法和优化技术的研究与应用是提高企业生产效率的基础和关键。因此,对车间调度问题的研究具有重要的现实意义和研究价值。
本文在综合国内外关于车间调度问题研究的基础上,考虑现行车间运作的实际情况,对车间调度问题进行了深入的研究。首先,对车间调度问题的含义、分类、特点和优化算法进行了系统的阐述,重点介绍了本文所采用的一种高效运行的算法——随机化算法。其次,本文建立了两个具有非线性混合整数规划特点的车间调度模型。一个是基于可重入和并行机特点的Job Shop调度模型,另一个是混合型车间调度模型,前者将车间调度的可重入性和并行机特点融合到Job Shop调度问题中,而后者综合了Flow Shop调度、Job Shop调度、可重入调度和并行机调度四类调度的特点,前者是后者的基础。最后,通过ILOG Scheduler、ILOG Solver和C++语言等设计随机化算法,并利用采集的西安XX公司生产线数据,对本文提出的混合型车间调度问题进行仿真优化,验证了模型和算法的可行性。
With the rapid development of technology and increasing global competition, the competition between manufacturing enterprises will be more drastic. In order to continuously improve and maintain the dominant position in the competition and core capability of competition, enterprises must strengthen their inner production management, especially its one of core-scheduling management. As a pillar and core of a whole enterprise, scheduling management is not only the meeting point of material flow, information flow and control flow, but also the foundation and root of realizing the entire company’s operation goal. The research and application of effective workshop scheduling methods and optimization techniques were the key elements to promote production efficiency. Therefore, it is of great realistic significance and research value to research workshop scheduling problem.
On the basis of the technical review on the domestic and foreign research,combining the actual workshop operation,an extensive study on workshop scheduling problem is carried out in this dissertation.Firstly, the conception,sorts,characteristics and optimization algorithms of workshop scheduling problem are described systematically, and randomization algorithm as a highly effective algorithm is introduced mainly. Secondly, the dissertation provides two workshop scheduling models which have characteristics of nonlinear mixed integer programming problem. One is Job Shop scheduling model which combines with re-entrant scheduling and parallel machine scheduling. Another is mixed workshop scheduling model which combines with Flow Shop scheduling, Job Shop scheduling, re-entrant scheduling and parallel machine scheduling. The former is the basis of the latter. Finally, through using actual data collected in production lines of one company in Xi’an, randomization algorithm designed by programming language such as ILOG Scheduler, ILOG Solver and C++, is used to simulate and optimize the mixed workshop scheduling model provided above, and then validate feasibility of the model and algorithm.
引文
[1]姚伟,李华.基于虚拟仿真的车间布局优化研究[J].管理观察,2008, 11:202-203.
[2]肖菊.数字化生产线性能评估系统研究[D].西安电子科技大学:硕士学位论文,2009, 1.
[3] Jones, A. and Rabelo, J.C. Survey of Job Shop Scheduling Techniques, NISTIR, National Institute of Standards and Technology. Gaithersburg. MD. http://www.mel.nist.gov/.1998, 1-17.
[4]徐俊刚,戴国忠,王宏安.生产调度理论和方法研究综述[J].计算机研究与发展, 2004,41(2):257-267.
[5] MengChu Zhou, MuDer Jeng.“Modeling, Analysis, Simulation, Scheduling, and Control of Semiconductor Manufacturing Systems: A Petri Net Approach”[J]. IEEE Transactions on Semiconductor Manufacturing, 1998, 11(3): 333-357.
[6] Ming-Hung Lin, Li-Chen Fu.“Modeling, Analysis, Simulation and Control of Semiconductor Manufacturing Systems: A Generalized Stochastic Colored Timed Petri Net Approach”, Systems, Man, and Cybernetics, 1999. IEEE SMC 99 Conference Proceedings, 1999, 13: 769-774.
[7] Feng Chu, Chengbin Chu, Caroline Desprez. Series production in a basic re-entrant shop to minimize makespan or total flow time[J]. Computers & Industrial Engineering, 2010, 58(2): 257-268.
[8] Stephen C.Grave, Harlan C.Meal, Daniel Stefek, Abdel Hamid Zeghmi. Scheduling of re-entrant flow shops[J]. Journal of Operations Management, 1983, 3(4): 197-207.
[9]王永,吴智铭,隋义.基于遗传算法的可重入半导体生产线的调度[J].计算机仿真,2007,24(12): 247-250.
[10]翟文彬.可重入制造系统的智能协同控制技术研究[D].上海交通大学:博士学位论文,2005,4.
[11]昌塞彦.基于规则的可重入生产系统调度问题研究[D].大连理工大学:博士学位论文,2005,9.
[12] Liao, C. J., Lin, C. H. Makespan minimization for two uniform parallel machines[J]. International Journal of Production Economics, 2003, 84:205–213.
[13] Liu, Y., Karimi, I. A. Scheduling multistage, multiproduct batch plants with nonidentical parallel units and unlimited intermediate storage[J]. Chemical Engineering Science, 2007, 62: 1549-1556.
[14]何敬东,黄向,严太山.并行机调度遗传算法研究[J].大众科技,2008, 6:54-55.
[15] J.C.Chen, K.H.Chen, J.J.Wu, C.W.Chen. A study of the flexible job shop scheduling problem with parallel machines and reentrant process[J].Int J Adv Manuf Technol, 2008, 39: 344-354.
[16]王凌.车间调度及其遗传算法[M].北京:清华大学出版杜,2003.
[17] Story, A. E. , Wagner, H. M. . Computational Experience whit Integer Programming for Job-Shop Scheduling[J].Industrial Scheduling,Chap.14, Prentice-Hall, 1963.
[18] Gavett, J. w. . Three Heuristic Rules for Sequencing Jobs to a Single Production Facility[J]. Mgmt. Sci. , 1965, 11: B166-B176.
[19] S. Panwalker, Wafik Iskander. A Survey of Scheduling[J]. Ops. Res. . 1977, 25(1): 45-61.
[20] M. S. Fox. ISIS: A Retrospective Intelligent Scheduling[J].Intelligent Scheduling, Kaufmann, ed: Michael B. Morgan, 1994: 3-28.
[21] Allaoui H, Artiba A. Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints[J]. Computers and Industrial Engineering (S0360-8352), 2004, 47(4): 431-450.
[22] Yailen Martinez, Bert Van Vreckem, David Catteeuw, Ann Nowe. Application of Learning Automata for Stochastic Online Scheduling[J]. Recent Advances in Optimization and its Appications in Engineering, 2010, 7: 491-498.
[23] Fariborz Jolai, Shaya Sheikh, Massoud Rabbani, Behrooz Karimi. A genetic algorithm for solving no-wait flexible flow lines with due window and job rejection[J]. Int J Adv Manuf Technol,2009, 42: 523-532.
[24]王竹卿.基于遗传算法的车间调度问题研究[D].大连理工大学:硕士学位论文,2006, 12.
[25] Jen-Shiang Chen. A branch and bound procedure for the reentrant permutation flow-shop scheduling problem[J]. Int J Adv Manuf Technol, 2006, 29: 1186-1193.
[26] Mohammad Saidi-Mehrabad, Parviz Fattahi. Flexible job shop scheduling with tabu search algorithms[J]. Int J Adv Manuf Technol, 2007, 32: 563-570.
[27]李霄蜂,史金飞,阎威武.混合流水车间调度的变邻域禁忌搜索算法[J].计算机工程,2008, 34(2l):10-11.
[28]刘志雄.调度问题中的粒子群优化方法及其应用研究[D].武汉理工大学:博士学位论文,2005,10.
[29]陈荣军,康国春.目标为带权总完工时问的两排序问题随机化算法[J].科学技术与工程,2008,8(21):1671-1819..
[30]陈荣军.一类串行工件同时加工排序问题的研究[J].常州工学院学报,2010, 23(2):67-70.
[31]白宏斌,杨建军,王健.基于约束满足的批量计划问题研究[J].现代制造工程, 2006,5:19-21.
[32]陈锐.制造业实时排程与重排程基础架构研究[D].西北工业大学:硕士学位论文,2006,11.
[33]杨达玲,杨建军.基于ILOG SOLVER的Job-Shop调度算法实现[J].现代制造工程,2006, 5: 22-24.
[34] George Steiner, Zhihui Xue. On the connection between a cyclic job shop and a reentrant flow shop scheduling problem[J]. J Sched, 2006,9: 381-387.
[35]石锦凤,冯斌,孙俊.求解job-shop调度问题的量子粒子群优化算法[J].计算机应用研究,2008, 25(3): 684-686.
[36]陈浩.遗传算法求解一类带工艺约束的并行机调度问题[D].中科技大学:硕士学位论文,2005, 8.
[37] Kim G. H, Lee G S. Genetic reinforcement learning approach to the heterogeneous machine scheduling problem[J]. IEEE Trans Robot Automation, 1999, 14(6): 879-893.
[38]李小华,熊禾根.基于粒子群算法的车间作业调度问题[J].信息技术,2009, 7: 19-21.
[39]李长明.随机搜索与最优搜索[J].军事运筹与系统工程,2001, 2: 18-20.
[40]陈皓,陈铁英.用遗传算法求解柔性作业车间调度问题[J].先进制造技术,2004, 23(4): 14-15.
[41]贾兆红.粒子群优化算法在柔性作业车间调度中的应用研究[D].中国科学技术大学:博士学位论文,2008, 4.
[42] Yue CAI, Jian WANG, Hua LI. A model for a special re-entrant flow shop scheduling[J]. The 2010 International Conference on Information, Electronic and Computer Science, 2010,3:1887-1891.
