柔性车间生产排产调度优化方法

摘要/Abstract

摘要： 为满足柔性制造企业在车间生产中合理安排生产排产调度的需要,提出柔性车间生产排产调度优化方法。首先,通过分析车间生产排产问题的特点,制定满足车间应用需求和各种资源限制的生产排产总体流程,从而设计基于约束条件的生产对象关系模型；其次,提出一种动态策略差分进化算法,根据个体之间的拥挤度动态选择变异策略,设计基于工序位置的编解码方案,其能快速有效地进行求解,从而得到最佳调度方案,提高设备运行效率,实现资源利用的最大化；最后,通过6个标准测试函数、FT6-6测试问题及生产调度应用实例验证了算法的有效性。

关键词: 生产排产调度,组合优化,差分进化,柔性制造

Abstract: To meet the needs of the production scheduling of flexible manufacturing enterprises,an optimization method for production scheduling was proposed.Firstly,an overall flow of the production scheduling which meets the workshop application requirements and various resource constraints is designed by analyzing the characteristics of the production scheduling problem in the enterprise workshop,and a constraint condition based production objective relation model is presented.Secondly,a differential evolution with dynamic strategy is proposed.In the proposed algorithm,the mutation strategy is dynamically selected according to the crowding degree between each individual in the current population.Moreover,a decoding scheme is designed based on the position of the process.Therefore,the optimal scheduling scheme is obtained to improve the operational efficiency of equipment to maximize the utilization of resources.Finally,the effectiveness of the proposed method is verified by six benchmark functions,FT6-6 scheduling problem and practical example.

Key words: Production scheduling,Combinatorial optimization,Differential evolution,Flexible manufacturing

张贵军,丁情,王柳静,周晓根. 柔性车间生产排产调度优化方法[J]. 计算机科学, 2018, 45(2): 269-275. https://doi.org/10.11896/j.issn.1002-137X.2018.02.046

ZHANG Gui-jun, DING Qing, WANG Liu-jing and ZHOU Xiao-gen. Optimization Method of Production Scheduling in Flexible Job[J]. Computer Science, 2018, 45(2): 269-275. https://doi.org/10.11896/j.issn.1002-137X.2018.02.046

参考文献

[1] ZHU X H,ZHU J F,JIANG T.Comparison of several models of job shop scheduling problem[J].Statistics and Decision,2007(23):174-176.(in Chinese) 朱星辉,朱金福,姜涛.作业车间调度问题的几种模型之比较[J].统计与决策,2007(23):174-176.
[2] BRUKER P,SCHLIC R.Job-shop Scheduling with Multi-purpose Machines[J].Computing,1990,4(2):369-375.
[3] 张智海.调度:原理、算法和系统[M].北京:清华大学出版社,2007.
[4] XIONG R,WU C.Technical status and development trend of workshop production scheduling problem[J].Journal of Tsinghua University,1998,38(10):55-60.(in Chinese) 熊锐,吴澄.车间生产调度问题的技术现状与发展趋势[J].清华大学学报,1998,38(10):55-60.
[5] GRAVES S C.A review of production scheduling[J].Opera-tions Research,1981,29(4):646-675.
[6] LIU M.A review of the research on production scheduling based on data[J].Acta automatica Sinica,2009,35(6):785-806.(in Chinese) 刘民.基于数据的生产过程调度方法研究综述[J].自动化学报,2009,35(6):785-806.
[7] CHEN I J,CHUNG C S.Sequential modeling of the Planning and Scheduling Problems of Flexible Manufacturing Systems[J].Journal of the Operational Research Society,1996,47(10):1216-1227.
[8] THOMALLA C S.Job shop scheduling with alternative process plans[J].International Journal of Production Economics,2001,74(1-3):125-134.
[9] ZUO Y,GONG M G,CENG J L,et al.Hybrid multi-objective algorithm for flexible job shop scheduling problem[J].Computer Science,2015,42(9):220-225.(in Chinese) 左益,公茂果,曾久琳,等.混合多目标算法用于柔性作业车间调度问题[J].计算机科学,2015,42(9):220-225.
[10] WEI X M.Application of ant colony algorithm based on mindevolution in typical production scheduling[J].Computer Science,2013,40(7):236-238,257.(in Chinese) 魏先民.基于思维进化的蚁群算法在典型生产调度中的应用[J].计算机科学,2013,40(7):236-238,257.
[11] SHAO X Y,LI X Y,GAO L,et al.Integration of process planning and scheduling——A modified genetic algorithm-based approach[J].Computers & Operations Research,2009,36(6):2082-2096.
[12] XIA W J,WU Z M.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems[J].Computers & Industrial Engineering,2005,48(2):409-425.
[13] STORN R,PRICE K.Differential evolution:a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.
[14] ZHOU X G,ZHANG G J,HAO X H,et al.A differential evolution algorithm based on local Lipschitz lower bound to estimate support surface[J].Chinese Journal of Computers,2016,39(12):2631-2651.(in Chinese) 周晓根,张贵军,郝小虎,等.一种基于局部Lipschitz下界估计支撑面的差分进化算法[J].计算机学报,2016,39(12):2631-2651.
[15] ZHOU X G,ZHANG G J,HAO X H.Differential evolution algorithm based on local abstract convex region[J].Acta automa-tica Sinica,2015,41(7):1315-1327.(in Chinese) 周晓根,张贵军,郝小虎.局部抽象凸区域剖分差分进化算法[J].自动化学报,2015,41(7):1315-1327.
[16] ZHOU X G,ZHANG G J,HAO X H,et al.Enhanced differen-tial evolution using local Lipschitz underestimate strategy for computationally expensive optimization problems[J].Applied Soft Computing,2016,48(11):169-181.
[17] LIU X P,XU B Z,PENG J,et al.Job shop scheduling model and its solution for concurrent work processes[J].Journal of Computer-aided Design & Computer Graphics,2012,24(1):120-127.(in Chinese) 刘晓平,徐本柱,彭军,等.工件工序可并行的作业车间调度模型与求解[J].计算机辅助设计与图形学学报,2012,24(1):120-127.
[18] CUI J S,LI T K,ZHANG W X.Hybrid flow shop scheduling model and its genetic algorithm[J].Journal of University of Scien-ce and Technology Beijing,2005,27(5):623-626.(in Chinese) 崔建双,李铁克,张文新.混合流水车间调度模型及其遗传算法[J].北京科技大学学报,2005,27(5):623-626.
[19] ZHOU X.Design and implementation of workshop schedulingsystem for distributed CNC system[D].Shenyang:University of Chinese Academy of Sciences,2014.(in Chinese) 周鑫.分布式数控系统车间排产系统的设计与实现[D].沈阳:中国科学院大学,2014.
[20] ZHOU X G,ZHANG G J,HAO X H,et al.A novel differential evolution algorithm using local abstract convex underestimate strategy for global optimization[J].Computers & Operation Research,2016,75(11):132-149.
[21] QIN A K,HUANG V L,SUGANTHAN P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation,2009,13(2):398-417.
[22] WANG Y,CAI Z,ZHANG Q.Differential evolution with composite trial vector generation strategies and control parameters[J].IEEE Transactions on Evolutionary Computation,2011,15(1):55-66.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed