改进回溯搜索算法求解多目标柔性作业车间调度问题  

Improved Backtracking Search Algorithm for Multi-objectiveFlexible Job Shop Scheduling Problem

作　　者：裴小兵[1] 戴毓彤 PEI Xiaobing;DAI Yutong(School of Management,Tianjin University of Technology,Tianjin 300384,China)

机构地区：[1]天津理工大学管理学院,天津300384

出　　处：《运筹与管理》2023年第5期9-15,共7页Operations Research and Management Science

基　　金：科技部创新方法专项项目(2017IM010800)。

摘　　要：随着绿色制造的到来,在调度问题中考虑能源消耗相关的目标变得至关重要,这已经成为了当下热点研究领域。因此,本文建立以最小化最大完工时间、机器总负荷和总能量消耗为目标的柔性作业车间调度数学模型。就回溯搜索算法的缺点提出改进,该算法通过结合改变个体搜索幅度因子对变异操作进行动态控制,防止种群迭代过程中陷入局部最优,然后通过结合个体引导与随机数扰乱提出一种新的交叉算子,提高后期寻优能力,防止了算法过早收敛。最后,运用基准算例对该算法的求解性进行了验证,并与文献中其他算法从求解精度、求解多样性、求解最优值等方面进行对比,结果表明该改进算法具有优越的求解性能。最后为该问题后续研究提供了三个可行方向:考虑更多约束条件、增加局部搜索算子和考虑实例分析。Nowadays,it is very important for enterprises to arrange limited resources and optimize specific performance.In addition,the production cycle has become one of the main factors of enterprise competition when the manufacturing cost varies little.With the development of lean production and just-in-time production,the production cycle of products is constantly shortened,and many researchers and practitioners focus on the design of a reasonable scheduling plan for all kinds of scheduling problems to improve market competitiveness.In recent decades,scheduling problem has been considered as a key problem affecting production efficiency.An expansion of the traditional job-shop scheduling difficulty in flexible manufacturing systems,the flexible job-shop scheduling problem is presented.Compared with many scheduling problems in the real world,the multi-objective flexible job-shop scheduling problem(MO-FJSP)usually involves the simultaneous optimization of multi-conflicting objectives to some extent.Therefore,MO-FJSP may be closer to the actual production environment,should be given enough attention,and continue to be conducted in-depth research.At the same time,with the advent of green manufacturing,reducing energy consumption of manufacturing enterprises is indispensable to sustainable development,and it is also an urgent problem to be solved by every manufacturing enterprise.It is necessary to develop energy-oriented methods to minimize energy consumption.So,the issue of energy target in scheduling is of great importance,and it has been the focus of attention in this area.For this reason,this thesis aims at building the MO-FJSP mathematic model and offering a solving way.Backtracking Search Algorithm(BSA)is a dual-population Algorithm,which uses the old population to guide the evolution of the new population.The traditional backtracking search algorithm has the disadvantages of weak discretization,premature convergence and limited local search ability.This paper applies the BSA to MO-FJSP,and proposes an Improved Backtr

关 键 词：柔性作业车间 生产调度 回溯搜索算法 多目标优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]