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

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

随着绿色制造的到来,在调度问题中考虑能源消耗相关的目标变得至关重要,这已经成为了当下热点研究领域。因此,本文建立以最小化最大完工时间、机器总负荷和总能量消耗为目标的柔性作业车间调度数学模型。就回溯搜索算法的缺点提出改进,该算法通过结合改变个体搜索幅度因子对变异操作进行动态控制,防止种群迭代过程中陷入局部最优,然后通过结合个体引导与随机数扰乱提出一种新的交叉算子,提高后期寻优能力,防止了算法过早收敛。最后,运用基准算例对该算法的求解性进行了验证,并与文献中其他算法从求解精度、求解多样性、求解最优值等方面进行对比,结果表明该改进算法具有优越的求解性能。最后为该问题后续研究提供了三个可行方向:考虑更多约束条件、增加局部搜索算子和考虑实例分析。

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 Backtracking Search Algorithm(IBSA)with Pareto sorting.Then the mutation operation is dynamically controlled by changing the individual search amplitude factor to widen the search direction.In the iterative process,the population will not be placed in the local optimal state.Because the backtracking search algorithm uses the old population to provide the direction for the search process,which results in the weakening of its late-stage search ability and the limitation of local search ability,a new crossover operator is proposed by combining individual guidance with random number disturbance,which improves the ability of late-stage optimization and prevents premature convergence.Lastly,a receiver criterion is proposed to further enhance the convergence ability of the algorithm.In order to verify the solvability of the algorithm,Kacem and Brandimarte series benchmark examples are used to simulate the algorithm,and the results of different multi-objective optimization algorithms are quantified.Compared with other methods,the proposed method is superior to that of other methods in diversity and optimal value.Finally,in view of this question,the proposed future research has three directions,which may carry on the further research:(1)Considering that there are more and more constraints in the actual manufacturing system,and the common problems such as machine tool failure,tool degradation and worker flexibility are increasing,IBSA can be applied to FJSP considering the actual constraints in the future,to improve the accuracy of the model.(2)Adding local search operator BSA is a global search algorithm,which has the disadvantage of weak local search ability.Local search plays an important role in balancing the search behavior of multi-objective evolutionary algorithms,so improving the efficiency of neighborhood search will directly affect the overall performance of hybrid algorithms.This paper focuses on the application of backtracking search algorithm in multi-objective combinatorial optimization problems,and in the future,we can further explore and improve the performance of BSA by integrating effective local search operators or using compound neighborhood structure,so as to find a way to circumvent local optimum.(3)In order to compare with other algorithms conveniently,the performance of the algorithm is simulated and verified by two classical benchmark examples in FJSP.In the future,the analysis should be combined with the enterprise case,in order to better contact with the industry practice.