技术领域Technical field
本技术方案是计算机应用技术领域，具体是一种基于SSA算法改进的多目标柔性车间调度方法。This technical solution is in the field of computer application technology, specifically a multi-objective flexible workshop scheduling method based on an improved SSA algorithm.
背景技术Background technique
离散制造是智能制造业的一种重要类型，与流程制造相对应。离散制造具有多品种和小批量生产的特点。为了应对市场的变化，许多企业选择采用柔性制造系统来提高生产的灵活性。这种灵活性使得生产过程更具有适应性。在我国的离散制造企业中，已有超过95％的企业采用了柔性制造系统。Discrete manufacturing is an important type of intelligent manufacturing and corresponds to process manufacturing. Discrete manufacturing is characterized by multi-variety and small-batch production. In order to cope with market changes, many companies choose to adopt flexible manufacturing systems to improve production flexibility. This flexibility makes the production process more adaptable. Among my country's discrete manufacturing companies, more than 95% have adopted flexible manufacturing systems.
生产调度的优劣直接决定了智能制造产业生产效率的高低，其核心是通过集成信息化和工业化，实现生产过程的智能化和自动化。通常来说，不同类型的生产订单，其所需要的生产设备等资源也不同，因此，需要根据不同的生产订单制定不同的生产调度方案，因此生产现场的复杂性也对生产提出了多种要求。为了响应实际生产需求，广大学者对多目标FJSP问题进行了研究。The quality of production scheduling directly determines the production efficiency of the intelligent manufacturing industry. Its core is to realize the intelligence and automation of the production process by integrating informatization and industrialization. Generally speaking, different types of production orders require different production equipment and other resources. Therefore, different production scheduling plans need to be formulated according to different production orders. Therefore, the complexity of the production site also puts forward various requirements for production. . In order to respond to actual production needs, many scholars have studied the multi-objective FJSP problem.
柔性作业车间调度问题FJSP(Flexible Job Shop Scheduling Problem)是一种柔性作业车间调度问题的重难题，这也成为了研究者研究的重点，研究表明，3台以上机器的流水线调度属于NP(NP-hard问题)难问题。在FJSP中，也就是柔性制造系统一个主要特点是一个工序可以在多台机器上进行加工，并且不同机器上的加工时间也不同。这样增加了调度过程的灵活性和便捷性，更符合现代制造业的实际情况。The Flexible Job Shop Scheduling Problem FJSP (Flexible Job Shop Scheduling Problem) is a difficult problem of flexible job shop scheduling, which has also become the focus of researchers' research. Research shows that the assembly line scheduling of more than 3 machines belongs to NP (NP- hard problem) difficult problem. In FJSP, a main feature of the flexible manufacturing system is that a process can be processed on multiple machines, and the processing time on different machines is also different. This increases the flexibility and convenience of the scheduling process and is more in line with the actual situation of modern manufacturing.
对于这种调度NP难问题，产生了以下三大类求解方法：For this kind of scheduling NP-hard problem, the following three major categories of solution methods have been produced:
首先是传统的最优化方法，对于最优化方法，主要包括数学规划法、拉格朗日松弛法、分枝定界法和枚举法等。数学规划法将FJSP问题建模为数学规划模型，并采用整数规划、动态规划和决策分析等方法来解决调度最优化问题。拉格朗日松弛法是一种以求解目标值下界为目的的方法。The first is the traditional optimization method. For optimization methods, it mainly includes mathematical programming method, Lagrangian relaxation method, branch-and-bound method and enumeration method. The mathematical programming method models the FJSP problem as a mathematical programming model, and uses integer programming, dynamic programming and decision analysis methods to solve the scheduling optimization problem. The Lagrangian relaxation method is a method aimed at finding the lower bound of the target value.
其次是启发式方法。尽管最优化方法可以用来求解最优解，但对于一些大规模甚至中等规模的调度问题，最优化方法往往难以应用。因此，在求解流水车间调度问题时，常常使用启发式算法。启发式方法的目标是通过探索各种替代方案来找到接近最优的调度计划，从而最大限度地降低生产成本。Next are heuristics. Although optimization methods can be used to find optimal solutions, for some large-scale or even medium-scale scheduling problems, optimization methods are often difficult to apply. Therefore, heuristic algorithms are often used when solving flow shop scheduling problems. The goal of heuristic methods is to find a near-optimal scheduling plan that minimizes production costs by exploring various alternatives.
基于启发式方法，许多研究人员提出元启发式方法，它将随机算法与局部搜索相结合，并包含各种群体智能优化算法。其中，松鼠觅食算法(Squirrel Search Algorithm，SSA)是最新的一种群体智能优化算法，具有高求解精度、强稳定性和适用于大规模问题等特点。然而，与其他智能优化算法一样，SSA算法仍然存在早熟收敛、局部最优和后期收敛速度慢等问题。Based on heuristic methods, many researchers have proposed meta-heuristic methods, which combine random algorithms with local search and include various swarm intelligence optimization algorithms. Among them, the Squirrel Search Algorithm (SSA) is the latest swarm intelligence optimization algorithm, which has the characteristics of high solution accuracy, strong stability, and suitability for large-scale problems. However, like other intelligent optimization algorithms, the SSA algorithm still has problems such as premature convergence, local optimality and slow convergence speed in the later period.
发明内容Contents of the invention
通过解决上述技术问题，本发明把改进之后的SSA算法应用于解决较大规模离散车间生产调度上，让SSA更加适合解决实际的多目标调度问题。By solving the above technical problems, the present invention applies the improved SSA algorithm to solving large-scale discrete workshop production scheduling, making SSA more suitable for solving actual multi-objective scheduling problems.
解决的步骤是：The solution steps are:
(1)给出车间生产的复杂情况，提出柔性车间调度问题，针对离散车间制造实际情况建立调度优化模型。(1) Given the complex situation of workshop production, a flexible workshop scheduling problem is proposed, and a scheduling optimization model is established based on the actual situation of discrete workshop manufacturing.
(2)通过编码解码的方式对离散的车间调度问题进行连续化处理。(2) Continuous processing of discrete workshop scheduling problems through encoding and decoding.
(3)改进传统的SSA算法，利用佳点集法改进初始种群位置，针对问题设计变邻域搜索算法提高局部搜索的准确度。(3) Improve the traditional SSA algorithm, use the best point set method to improve the initial population position, and design a variable neighborhood search algorithm according to the problem to improve the accuracy of local search.
(4)寻找最适合求解多目标调度问题的调度序列的方法。(4) Find the most suitable scheduling sequence method for solving multi-objective scheduling problems.
在步骤(1)中的分析车间生产情况，这里的工作主要是在分析实际车间可能会产生的问题，发现因为车间情况复杂但是作业调度安排灵活，往往需要多个指标用来得到最优的调度计划。当两个或多个目标同时优化时，减少一个功能可能会导致另一个或多个功能增加。这使得双目标或多目标FJSP比单目标FJSP更难求解，但是会获得FJSP高质量解决方案的结果。In the analysis of workshop production conditions in step (1), the work here is mainly to analyze the problems that may arise in the actual workshop. It is found that because the workshop situation is complex but the job scheduling is flexible, multiple indicators are often needed to obtain optimal scheduling. plan. When two or more goals are optimized simultaneously, reducing one feature may lead to an increase in another or more features. This makes dual-objective or multi-objective FJSP more difficult to solve than single-objective FJSP, but results in high-quality solutions of FJSP are obtained.
面对求解FJSP问题，使用群体智能优化算法的就需要对其数据进行编码解码处理，也就是MES系统的生产过程产生的数据，把这些数据放到模型中进行计算。这些数据属于离散数据，如果需要用智能优化算法求解首先需要将离散的数据连续化，这里本发明就是将调度计划编码成连续数据，模型计算求解得到的结果再将其解码成最优的调度计划如图1。这里使用MSOS编码方式来进行编码解码。When facing the problem of solving FJSP, those who use the swarm intelligence optimization algorithm need to encode and decode the data, which is the data generated by the production process of the MES system, and put these data into the model for calculation. These data are discrete data. If you need to use intelligent optimization algorithms to solve the problem, you first need to make the discrete data continuous. Here, the present invention encodes the scheduling plan into continuous data, and then decodes the results obtained by the model calculation into the optimal scheduling plan. Figure 1. MSOS encoding is used here for encoding and decoding.
改进1，对松鼠觅食算法SSA进行改进方法为：SSA算法初始种群均匀分布可确保种群的多样性和遍历性，提高算法的搜索性，在原始SSA中采用随机初始化种群个体，难以保证种群的多样性。佳点集是一种分布均匀、有效的选点方式，利用佳点集的均匀性初始化种群，可以提高种群的多样性。通过和随机分布与Tent混沌映射的比较，可以看出佳点集更加均匀分布，且效果误差更小。Improvement 1. The improvement method for the squirrel foraging algorithm SSA is as follows: the uniform distribution of the initial population of the SSA algorithm can ensure the diversity and traversability of the population, and improve the searchability of the algorithm. In the original SSA, random initialization of population individuals is used, which is difficult to ensure the stability of the population. Diversity. The best point set is an evenly distributed and effective point selection method. Using the uniformity of the best point set to initialize the population can improve the diversity of the population. By comparing with random distribution and Tent chaotic mapping, it can be seen that the best point set is more evenly distributed and the effect error is smaller.
改进2，对松鼠觅食算法SSA进行改进方法为：结合SSA算法特点引入变邻域搜索算法VNS，在不降低原算法收敛速度快优点的基础上，使算法的搜索能力更加灵活。Improvement 2. The method to improve the squirrel foraging algorithm SSA is to introduce the variable neighborhood search algorithm VNS based on the characteristics of the SSA algorithm, making the search ability of the algorithm more flexible without reducing the advantage of the original algorithm's fast convergence speed.
改进后的变邻域搜索，对SSA共有两次修改过程：第一次修改采用SSA方法(采取当迭代处于一半的时候，SSA算法向最优解快速靠拢的独特更新机制进行更新个体位置)使个体跳跃到当前全局最优位置的附近，用来向最优解快速靠拢；第二次修改采用VNS方法，即对初始解和经过初步搜索的中间解进行局部搜索，以期稳定的优化结果，提升局部搜索的精度。改进后的变邻域搜索既充分利用了当前最优解个体的位置信息，又充分利用了全局最优解的位置信息，寻优更加灵活，以此来克服SSA容易陷入局部最优解的问题。The improved variable neighborhood search has two modification processes for SSA: the first modification adopts the SSA method (when the iteration is in half, the unique update mechanism of the SSA algorithm to quickly move closer to the optimal solution is used to update the individual position). The individual jumps to the vicinity of the current global optimal position to quickly move closer to the optimal solution; the second modification adopts the VNS method, that is, a local search is performed on the initial solution and the intermediate solution after preliminary search, in order to stabilize the optimization results and improve Accuracy of local search. The improved variable neighborhood search not only makes full use of the position information of the current optimal solution individual, but also makes full use of the position information of the global optimal solution, making the optimization more flexible, thereby overcoming the problem that SSA easily falls into the local optimal solution. .
改进3，改进之后的智能优化算法SSA还是无法求解多目标问题，本发明建立外部记忆库存储SSA算法求解中的非劣解，采取Pareto最优解集用来求解多目标FJSP问题，并进行模糊决策法改进多目标求解，对Pareto最优解集进行计算解的满意度，最终得到最优解。Improvement 3. The improved intelligent optimization algorithm SSA is still unable to solve multi-objective problems. The present invention establishes an external memory bank to store the non-inferior solutions in the SSA algorithm solution, adopts the Pareto optimal solution set to solve the multi-objective FJSP problem, and performs fuzzy The decision-making method improves multi-objective solving, calculates the satisfaction of the solution to the Pareto optimal solution set, and finally obtains the optimal solution.
附图说明Description of drawings
图1是智能优化算法求解离散车间问题的一般流程图；Figure 1 is a general flow chart of intelligent optimization algorithm for solving discrete workshop problems;
图2是MSOS编码方式调度序列示意图；Figure 2 is a schematic diagram of the MSOS coding mode scheduling sequence;
图3是SSA不同种群分布的差异示意图；Figure 3 is a schematic diagram of the differences in distribution of different populations in SSA;
图4是两种不同的初始种群定位方法效果图；Figure 4 is a rendering of two different initial population positioning methods;
图5是不同方法的频率分布直方图；Figure 5 is the frequency distribution histogram of different methods;
图6是邻域搜索算法示意图；Figure 6 is a schematic diagram of the neighborhood search algorithm;
图7是SSA改进之后适应度收敛曲线图；Figure 7 is the fitness convergence curve after SSA improvement;
图8是Pareto最优前沿示意图；Figure 8 is a schematic diagram of the Pareto optimal front;
图9是模糊隶属度函数示意图；Figure 9 is a schematic diagram of the fuzzy membership function;
图10是改进后的SSA算法求解多目标柔性车间调度问题流程图；Figure 10 is a flow chart of the improved SSA algorithm for solving the multi-objective flexible workshop scheduling problem;
图11是改进后SSA求解多目标FJSP问题的算法流程图；Figure 11 is the algorithm flow chart of the improved SSA for solving the multi-objective FJSP problem;
图12是某个离散车间管理系统架构图；Figure 12 is an architecture diagram of a discrete workshop management system;
图13是智能调度子系统信息处理流程图Figure 13 is the information processing flow chart of the intelligent dispatch subsystem
具体实施方式Detailed ways
本发明是一种基于改进SSA算法的多目标柔性车间调度方法，步骤包括：1)针对实际的离散车间问题建立多目标柔性车间调度模型；2)通过MSOS编码方式对离散的车间调度数据进行连续化处理；3)使用改进的SSA智能优化算法求解连续化后的车间调度问题；对传统的SSA进行改进，利用佳点集法改进初始种群位置，通过变邻域搜索算法提高局部搜索的准确度；4)建立外部记忆库存储算法求解中的非劣解，使用Pareto最优解集和模糊决策法求解并获取多目标柔性车间调度问题的最优解，解码为最佳调度计划。The invention is a multi-objective flexible workshop scheduling method based on an improved SSA algorithm. The steps include: 1) establishing a multi-objective flexible workshop scheduling model for actual discrete workshop problems; 2) continuously processing discrete workshop scheduling data through MSOS coding. processing; 3) Use the improved SSA intelligent optimization algorithm to solve the continuous workshop scheduling problem; improve the traditional SSA, use the best point set method to improve the initial population position, and use the variable neighborhood search algorithm to improve the accuracy of local search ; 4) Establish an external memory bank to store the non-inferior solutions in the algorithm solution, use Pareto optimal solution set and fuzzy decision-making method to solve and obtain the optimal solution to the multi-objective flexible workshop scheduling problem, and decode it into the optimal scheduling plan.
本方法可以应用到生产制造执行MES系统中的智能调度子系统功能模块。This method can be applied to the intelligent scheduling subsystem functional module in the manufacturing execution MES system.
本发明模型核心就是智能优化算法SSA，可以把生产调度数据通过算法迭代逐步得到最优解调度计划，需要先对离散的车间调度问题进行连续化处理。经过对传统的SSA进行算法改进，克服SSA在求解柔性车间调度问题时初始种群分布不均匀和易陷入局部最优解的问题。The core of the model of the present invention is the intelligent optimization algorithm SSA, which can gradually obtain the optimal solution scheduling plan by iterating the production scheduling data through the algorithm. It is necessary to first continuously process the discrete workshop scheduling problem. After improving the algorithm of traditional SSA, it overcomes the problem of uneven initial population distribution and easy falling into local optimal solution when SSA solves the flexible workshop scheduling problem.
下面结合具体实施方式对本发明进一步说明：The present invention will be further described below in conjunction with specific embodiments:
1、传统SSA介绍：1. Introduction to traditional SSA:
SSA是最新出现的一种基于松鼠搜索态度的群体智能优化算法，松鼠个体通过以下四个步骤来进行移动：初始化种群，动态觅食行为，季节适应来更新位置，冬季末随机重新定位。该算法就是模仿飞行松鼠群体的觅食行为来在解空间内寻找最优解。SSA is the latest group intelligence optimization algorithm based on the search attitude of squirrels. Individual squirrels move through the following four steps: initializing the population, dynamic foraging behavior, updating positions through seasonal adaptation, and randomly relocating at the end of winter. This algorithm imitates the foraging behavior of the flying squirrel group to find the optimal solution in the solution space.
2、改进SSA并解决多目标柔型车间调度问题2. Improve SSA and solve the multi-objective flexible workshop scheduling problem
随着生产技术的发展，企业对于柔性作业车间调度问题FJSP问题的关注目标逐渐增多。为了得到实用的FJSP问题模型，研究者们提出了多种评价指标。在早期，性能评价主要以总时间或平均时间为指标。然而，随着需求变化和业务特点的考虑，研究者们提出了更多的评价指标来量化FJSP问题的性能。常见的评价指标有基于工件的性能指标，包括时间、交货期、成本；还有基于设备的效率指标，包括机器负荷、调度稳定性。这里以实际电子离散制造企业为例，车间生产的目标函数通常为最小化最长加工时间，进行建模。但是往往这点还不够，因为柔性车间生产现场可能会出现其他的问题。比如说生产现场会包含管理仓库作业的结果记录、核对和管理，对仓库作业过程的指导和规范，从而确定库存决策信息的准确。盘点仓库物料详情，会有出入库、调拨、盘点、销售、采购、发货这个一系列的管理，都和仓库的运行相关，本质上就是最小化仓储成本。针对这些FJSP问题的评价指标，建立下面的调度数学模型。With the development of production technology, enterprises are gradually paying more and more attention to the flexible job shop scheduling problem FJSP. In order to obtain a practical FJSP problem model, researchers have proposed a variety of evaluation indicators. In the early days, performance evaluation was mainly based on total time or average time. However, with changes in requirements and consideration of business characteristics, researchers have proposed more evaluation indicators to quantify the performance of FJSP problems. Common evaluation indicators include workpiece-based performance indicators, including time, delivery date, and cost; and equipment-based efficiency indicators, including machine load and scheduling stability. Here, an actual electronic discrete manufacturing enterprise is taken as an example. The objective function of workshop production is usually to minimize the maximum processing time for modeling. But often this is not enough, because other problems may occur at the flexible workshop production site. For example, the production site will include the management of warehouse operation result records, verification and management, and guidance and standardization of the warehouse operation process to ensure the accuracy of inventory decision-making information. Taking stock of the details of warehouse materials, there will be a series of management including incoming and outgoing, allocation, inventory, sales, purchasing, and delivery, which are all related to the operation of the warehouse. In essence, it is to minimize warehousing costs. Based on the evaluation indicators of these FJSP problems, the following scheduling mathematical model is established.
本发明所述车间柔性调度模型是指：有i个工件、m台机器，每个工件均有多道工序，每道工序将被安排在1～m台机器上生产，且生产时间不同。以最优化目标下的车间调度序列为调度方法，首先考虑到是最常见的时间因素，需要做到所有工件中最大的完成时间最小；其次结合目前现有的系统会出现库存紧张的情况，提出最小最大完成时间(最大完成时间的最小值)和最小仓储成本的柔性作业车间多目标(最小最大完成时间、最小仓储成本这两个目标)调度问题可以描述为以下数学模型：The workshop flexible scheduling model of the present invention refers to: there are i workpieces and m machines, each workpiece has multiple processes, and each process will be arranged to be produced on 1 to m machines, and the production time is different. Taking the workshop scheduling sequence under the optimization goal as the scheduling method, first of all, taking into account the most common time factor, it is necessary to minimize the maximum completion time of all workpieces; secondly, combined with the current inventory shortage situation in the existing system, it is proposed The flexible job shop multi-objective (minimum and maximum completion time, minimum warehousing cost) scheduling problem of minimum and maximum completion time (minimum of maximum completion time) and minimum warehousing cost can be described as the following mathematical model:
min F＝min(F1，F2)#(1)min F＝min(F1 , F2 )#(1)
Ci表示工件Ji的完工时间；α1为未完成工件仓储费率；α2为已完成工件仓储费率；sij和hij分别为开始加工时刻、完工时刻；Zijk∈{0，1}为工件Ji的第j道工序是否选择机器k为加工机器；Qijk为Oij不包含工序转运时间的加工耗时；Wijuvk为决策变量，值为1表示工序Jij将工序Juv作为后继工序，且二者均选择机器k进行加工，否则值为0。Ci represents the completion time of workpiece Ji ; α1 is the warehousing rate for unfinished workpieces; α2 is the warehousing rate for completed workpieces; sij and hij are the start time and completion time respectively; Zijk ∈{0, 1} is whether to select machine k as the processing machine for the jth process of workpiece Ji ; Qijk is the processing time of Oij excluding the process transfer time; Wiijuvk is the decision variable, and a value of 1 means that process Jij will replace process Juv is used as the subsequent process, and both machine k is selected for processing, otherwise the value is 0.
下表是对多目标函数F的实际生产中的约束条件：The following table shows the constraints in actual production of the multi-objective function F:
表1实际生产中的约束Table 1 Constraints in actual production
但是由于实际生产数据导致车间调度问题属于离散问题，因此需要对离散的车间调度问题进行连续化，才可以使用SSA算法来求解问题。However, due to the actual production data, the workshop scheduling problem is a discrete problem. Therefore, the discrete workshop scheduling problem needs to be continuous before the SSA algorithm can be used to solve the problem.
2.1离散调度车间问题连续化2.1 Continuousization of discrete scheduling workshop problems
车间调度问题的求解本质上是求得最优化目标下的调度序列，其中，Oij代表工件i的第j道工序，Mi，j代表Oi，j的可用机器数，机器的加工是非抢占式的，同一时刻一台机器只能加工一道工序且不可中断，只有在上一道工序完成才可进行下一道工序的加工，使用MSOS编码方式来表示一个调度序列：The solution to the workshop scheduling problem is essentially to obtain the scheduling sequence under the optimization objective, where Oij represents the jth process of workpiece i, Mi, j represents the number of available machines for Oi, j , and the processing of the machine is non-preemptive. Formula, a machine can only process one process at the same time and cannot be interrupted. The next process can only be processed after the previous process is completed. MSOS coding is used to represent a scheduling sequence:
(1)编码方式(1)Encoding method
MSOS编码方式对应FJSP问题的两个子问题，码段中包括机器码部分和工序码部分，分别代表工序将要分配的机器和工序在分配机器上的排序的信息。MSOS编码分为等长的两部分，MS为机器码部分表示机器选择信息，OS为工序码部分工件表示工序排序信息。通过MSOS编码的个体维度d为在机器码部分，将工序使用的机器转换为该维度的数值。在工序码部分，工件出现的次数就是该工件对应的加工顺序。MSOS编码的机器码部分和工序码部分的编码方式如下：The MSOS coding method corresponds to the two sub-problems of the FJSP problem. The code segment includes a machine code part and a process code part, which respectively represent information about the machine to which the process will be allocated and the ordering of the process on the allocated machine. The MSOS code is divided into two parts of equal length. MS is the machine code part that represents machine selection information, and OS is the process code part that represents process sequencing information. The individual dimension d encoded by MSOS is In the machine code part, convert the machine used in the process into the value of this dimension. In the process code part, the number of times a workpiece appears is the corresponding processing sequence of the workpiece. The encoding method of the machine code part and process code part of MSOS encoding is as follows:
Oij＝k，0＜k＜Mi，j，k∈N，Oi，j＝i#(4)Oij =k, 0＜k＜Mi,j , k∈N, Oi,j =i#(4)
(2)个体空间转换方式(2) Individual space transformation method
由于机器的下标是整数，因此机器码的部分取值必须是自然数，为了研究方便，将个体空间转换的解空间定义为一个取值为自然数的离散化解空间。对连续空间位置转换成离散空间位置的方式为：对于连续空间前一半维度的值，以下式取值为连续空间和离散空间共有的整数值Since the subscript of the machine is an integer, some values of the machine code must be natural numbers. For the convenience of research, the solution space of individual space transformation is defined as a discrete solution space whose values are natural numbers. The way to convert a continuous space position into a discrete space position is: for the value of the first half dimension of the continuous space, the value of the following formula is an integer value common to both continuous space and discrete space
式中F为连续空间取值，Fd为对应的离散空间取值。函数lower(Ωij)和upper(Ωij)分别表示Ωij的下限和上限，其中Ωij表示什么工序Oij的可用设备集。对于连续空间后一半维度的值，通过下式处理：idx＝fidx(sortasc(X)，X)，其中idx为索引数组。按大小进行排序，每一维度对应的索引值就是其对应离散空间该维度的值。In the formula, F is the continuous space value, and Fd is the corresponding discrete space value. The functions lower(Ωij ) and upper(Ωij ) represent the lower limit and upper limit of Ωij respectively, where Ωij represents the available equipment set of what process Oij . For the value of the last half dimension of the continuous space, it is processed by the following formula: idx=fidx (sortasc (X), X), where idx is the index array. Sorting by size, the index value corresponding to each dimension is the value of that dimension in the corresponding discrete space.
通过以上方式，松鼠种群中每个个体都持有一个柔性作业车间调度序列，当连续空间中的个体移动时，对应的也在离散空间中移动。算法通过迭代更新，在解空间中找到全局最优解。Through the above method, each individual in the squirrel population holds a flexible job shop scheduling sequence. When an individual in the continuous space moves, the corresponding one also moves in the discrete space. The algorithm finds the global optimal solution in the solution space through iterative updates.
(3)解码方式(3)Decoding method
通过个体空间转换的方式，将连续空间的解转换为离散空间的解后，将离散空间的解转换成调度序列如下式：Through individual space transformation, after converting the solution of continuous space into the solution of discrete space, the solution of discrete space is converted into the scheduling sequence as follows:
Oijm＝Fd，Oj＝f(Ωj，idx)#(6)Oijm =Fd , Oj =f(Ωj , idx)#(6)
Oijm表示工序Oi，j在机器Fd上加工，Oj表示将获取的索引值按从小到大分配给工序构成的离散空间。将机器码段对应的Fd按从左到右的顺序分配给按工件、工序序号从小到大排列的工序，将工序码段将从左到右的索引值取值分配给按工件、工序序号从小到大排列的工序，表示该工序是第几个加工。图2为解码过程，当每一工序均分配完加工机器和加工顺序后，通过工序插入方法将这一序列转换为可行的调度序列。Oijm indicates that the process Oi, j is processed on the machine Fd , and Oj indicates that the obtained index values are allocated to the discrete space composed of the process in ascending order. The Fd corresponding to the machine code segment is assigned from left to right to the processes arranged by workpiece and process number from small to large, and the process code segment is assigned the index value from left to right to the workpiece and process number. The processes arranged from small to large indicate which process the process is. Figure 2 shows the decoding process. After each process is assigned a processing machine and processing sequence, this sequence is converted into a feasible scheduling sequence through the process insertion method.
本发明对离散的车间调度问题进行连续化，从而可以使用SSA来求解多目标车间调度问题。本发明还对传统的SSA进行改进，克服了SSA在求解较大规模的问题时，存在的初始种群分布不均匀和易陷入局部最优解的问题。The present invention serializes discrete workshop scheduling problems, so that SSA can be used to solve multi-objective workshop scheduling problems. The present invention also improves traditional SSA and overcomes the problems of uneven initial population distribution and easy falling into local optimal solutions when SSA solves large-scale problems.
2.2SSA改进2.2SSA improvements
SSA具有很好的搜索能力，但算法的探索能力不强，收敛精度难以达到较高要求。下面从两个方面改进了SSA算法。第一种是利用佳点集法改进初始位置。二是增加最优位置对整体种群的影响，而不是像原算法那样只使用全局最优位置引导的进化算法。SSA has good search ability, but the algorithm’s exploration ability is not strong, and the convergence accuracy is difficult to meet high requirements. The SSA algorithm is improved in two aspects below. The first is to use the best point set method to improve the initial position. The second is to increase the impact of the optimal position on the entire population, instead of using only the evolutionary algorithm guided by the global optimal position like the original algorithm.
2.2.1利用佳点集法改进初始种群位置2.2.1 Use the best point set method to improve the initial population position
在大多数优化算法中，初始总体方法是基于均匀随机分布的。已知SSA优化算法每次迭代的结果与上一代种群有一定的关系如图3，种群的分布会导致最优解和最终迭代计算得到的结果相差很大。许多研究者使用不同的初始种群定位方法来改进算法，改进算法的计算结果比原算法更精确。因此，改进初始种群的分布在一定程度上影响最终结果和迭代次数，可以提高算法的收敛速度。均匀随机分布的初始种群位置不能均匀地覆盖整个解空间。而佳点集法可以满足这一要求。佳点集是由我国数学家华罗庚等提出，其原理为：设Gs是s维欧氏空间中的单位立方体，如果r∈Gs，形为：In most optimization algorithms, the initial population approach is based on a uniform random distribution. It is known that the result of each iteration of the SSA optimization algorithm has a certain relationship with the previous generation population, as shown in Figure 3. The distribution of the population will cause a large difference between the optimal solution and the final iterative calculation result. Many researchers use different initial population positioning methods to improve the algorithm, and the calculation results of the improved algorithm are more accurate than the original algorithm. Therefore, improving the distribution of the initial population affects the final result and the number of iterations to a certain extent, and can improve the convergence speed of the algorithm. Uniformly randomly distributed initial population positions cannot cover the entire solution space uniformly. The best point set method can meet this requirement. The best point set was proposed by Chinese mathematician Hua Luogeng and others. Its principle is: Suppose Gs is a unit cube in s-dimensional Euclidean space. If r∈Gs , the form is:
其偏差满足/>其中C(r，ε)h-1+ε是只与r和ε(ε是任意的正数)有关的常数，则称Ph(t)为佳点集，r为佳点。/>代表表取小数部分，h表示点数，取r＝{2cos(2πt/p)，1≤t≤s}是满足(p-3)/2≥s的最小素数，将其映射到搜索空间为：its deviation Satisfied/> Among them, C(r, ε)h-1+ε is a constant related only to r and ε (ε is any positive number), then Ph (t) is called the best point set, and r is the best point. /> The decimal part of the representative table is taken, h represents the number of points, r={2cos(2πt/p), 1≤t≤s} is the smallest prime number that satisfies (p-3)/2≥s, and it is mapped to the search space as:
xi(j)＝(ubj-lbj)·{rj(i)·t}+lbj#(8)xi (j)=(ubj -lbj )·{rj(i) ·t}+lbj #(8)
ubj和lbj表示第j维的上下界。ubj and lbj represent the upper and lower bounds of the jth dimension.
图4分别显示了随机条件和佳点集法生成100个个体的点集。可以清楚地看到，佳点集法生成的点集空间分布更加均匀。与佳点集法相比，均匀随机分布产生的初始位置存在团块和重叠现象。更进一步，当初始种群数量一定时，佳点集法的分布更加稳定。Figure 4 shows the random conditions and optimal point set method to generate point sets of 100 individuals respectively. It can be clearly seen that the spatial distribution of point sets generated by the optimal point set method is more uniform. Compared with the best point set method, the initial positions generated by uniform random distribution have clumps and overlaps. Furthermore, when the initial population size is constant, the distribution of the best point set method is more stable.
本发明加入佳点集使初始种群更加均匀，提升了种群多样性，将其嵌入到SSA算法的过程中可增加种群的多样性，有利于摆脱局部最值的吸引。但是往往均匀分布还不够，种群的初始化就需要随机性的体现。而Tent混沌作为一种非线性的自然现象，以其混沌序列具有遍历性、随机性等优点。实验设定初始种群个数为1000个，其中Tent混沌映射的映射参数为0.6、初始值为0.5得到佳点集和Tent混沌映射的频率分布直方图如图5，可以看出佳点集成均匀分布，且频率分布的效果较Tent误差更小随机性也更加好，在初始化过程中可增加种群的多样性，有利于摆脱局部最值的吸引。The present invention adds the best point set to make the initial population more uniform and improves the diversity of the population. Embedding it into the process of the SSA algorithm can increase the diversity of the population and help get rid of the attraction of local maximum values. But uniform distribution is often not enough, and the initialization of the population requires randomness. As a nonlinear natural phenomenon, Tent chaos has the advantages of ergodicity and randomness in its chaotic sequence. The experiment set the initial population number to 1000, in which the mapping parameter of Tent chaos map is 0.6 and the initial value is 0.5. The frequency distribution histogram of the best point set and Tent chaos map is obtained as shown in Figure 5. It can be seen that the best point integration is uniformly distributed. , and the frequency distribution effect is smaller and more random than Tent error. It can increase the diversity of the population during the initialization process, which is helpful to get rid of the attraction of local maximum values.
2.2.2变邻域搜索算法改进SSA搜索2.2.2 Variable neighborhood search algorithm improves SSA search
SSA可能容易受到启动环境的影响，并且容易陷入局部最优状态，通过引入更多的策略来扩展算法的探索和开发能力，可以提高算法的性能。许多研究学者大多会采用局部搜索来提高收敛性。但多目标求解下持续的局部搜索会导致种群收敛到几个点，非支配解集的解会减少，多样性也会减少。SSA may be susceptible to the influence of the startup environment and easily fall into a local optimal state. The performance of the algorithm can be improved by introducing more strategies to expand the algorithm's exploration and development capabilities. Many researchers mostly use local search to improve convergence. However, continuous local search under multi-objective solution will cause the population to converge to a few points, the number of solutions in the non-dominated solution set will decrease, and the diversity will also decrease.
面对这个问题，本发明提出变邻域搜索算法(Variable Neighborhood Search，VNS)来改进SSA搜索。VNS其主要思想是：采用多个不同的邻域进行系统搜索。首先采用最小的邻域搜索，当无法改进解时，则切换到稍大一点的邻域。如果能继续改进解，则退回到最小的邻域，否则继续切换到更大的邻域。优点是能利用不同的动作构成的邻域结构进行交替搜索，在集中性和疏散性之间达到很好的平衡如图6。VNS的研究最主要集中在邻域结构的设计、邻域内的局部搜索策略的选择，以及如何跳出局部最优解等三个方面。邻域结构定义的不同，可行解的数量和分布都会不同，因此会影响算法的运行效率，针对某离散车间实际生产问题，本发明提出包含如下3种邻域结构：Faced with this problem, the present invention proposes a variable neighborhood search algorithm (Variable Neighborhood Search, VNS) to improve SSA search. The main idea of VNS is to use multiple different neighborhoods for systematic search. First use the smallest neighborhood search, and when the solution cannot be improved, switch to a slightly larger neighborhood. If the solution can continue to be improved, return to the smallest neighborhood, otherwise continue to switch to a larger neighborhood. The advantage is that it can use the neighborhood structure composed of different actions to conduct alternate searches, achieving a good balance between centralization and dispersion as shown in Figure 6. The research on VNS mainly focuses on three aspects: the design of neighborhood structure, the selection of local search strategies within the neighborhood, and how to jump out of the local optimal solution. Different definitions of neighborhood structures will result in different numbers and distributions of feasible solutions, which will affect the operating efficiency of the algorithm. In view of the actual production problems of a discrete workshop, the present invention proposes the following three neighborhood structures:
1)邻域结构N1：在工序排序编码中任选2个不同位置，且这2个位置上的工序属于不同工件，将这2道工序位置互换，编码中其他工序位置保持不变。1) Neighborhood structure N1: Select any two different positions in the process sequence coding, and the processes at these two positions belong to different workpieces. The positions of these two processes are interchanged, and the positions of other processes in the coding remain unchanged.
2)邻域结构N2：在工序排序编码中任选2个不同位置，将靠后位置上的工序插入到靠前位置工序之前，其他工序位置保持不变。2) Neighborhood structure N2: Select any two different positions in the process sorting code, insert the process at the rear position before the process at the front position, and keep the positions of other processes unchanged.
3)邻域结构N3：在机器选择编码中随机选择1个位置，该位置对应工序能够选择的加工机器数应该大于1，然后从可选加工机器集中任选一台不同机器进行替换。其变邻域搜索过程伪代码如下:3) Neighborhood structure N3: Randomly select a position in the machine selection code. The number of processing machines that can be selected for the corresponding process at this position should be greater than 1, and then select a different machine from the set of optional processing machines for replacement. The pseudo code of its variable neighborhood search process is as follows:
对于邻域内的局部搜索策略的选择，本发明采用阈值接受法，阈值接受法设置:阈值ψ＞0，局部搜索迭代次数ρ←1，邻域选择参数θ←1及局部搜索终止迭代次数ρmax，初始解为X'，Cmax(X')表示X'在目标空间中适应度值。具体操作过程伪代码如下:For the selection of the local search strategy in the neighborhood, the present invention adopts the threshold acceptance method. The threshold acceptance method sets: threshold ψ>0, local search iteration number ρ←1, neighborhood selection parameter θ←1 and local search termination iteration number ρmax , the initial solution is X', and Cmax(X') represents the fitness value of X' in the target space. The specific operation process pseudo code is as follows:
对于如何跳出局部最优解，就是算法达到最大迭代次数的时候退出变邻域搜索，输出搜索到的当前解。改进后的SSA局部搜索共经历了两个修改过程。首先，在第一次修改中，采用了SSA方法。当迭代处于总迭代的一半时，SSA算法具有向最优解快速靠拢的独特更新机制进行更新位置，然后继续进行迭代得到中间解。As for how to jump out of the local optimal solution, the algorithm exits the variable neighborhood search when it reaches the maximum number of iterations and outputs the current solution found. The improved SSA local search has gone through two modification processes. First, in the first modification, the SSA method was adopted. When the iteration is half of the total iteration, the SSA algorithm has a unique update mechanism that quickly moves closer to the optimal solution to update the position, and then continues iteration to obtain the intermediate solution.
接着，在第二次修改中，采用了VNS方法。它对初始解和经过位置更新后得到的中间解进行局部搜索，以稳定优化结果，并提高局部搜索的准确度。VNS方法能够有效地利用之前搜索得到的信息，进一步优化解的质量。这样做的目的是使个体能够跳出局部最优解的影响，从而达到更好的探索全局最优解的能力。Then, in the second modification, the VNS method was adopted. It performs local search on the initial solution and the intermediate solution obtained after position update to stabilize the optimization results and improve the accuracy of local search. The VNS method can effectively utilize the information obtained from previous searches to further optimize the quality of the solution. The purpose of this is to enable individuals to escape the influence of the local optimal solution, thereby achieving better ability to explore the global optimal solution.
总的来说，改进后的SSA局部搜索有助于SSA算法跳出局部最优解。同时本发明与前期全局最优解进行比较而选择，用来维持种群多样性，也是为了防止前期过早陷入聚集。本发明对原始的SSA和改进之后SSA选用标准测试函数TF1的收敛曲线，改进的佳点集和变邻域搜索中各函数的定义域均采用了文献推荐取值，SSA种群大小为50，迭代次数为100，图7(a)采用原始随机初始化和加入佳点集初始化种群改进的SSA，图7(b)加入佳点集初始化种群和采用变邻域搜索改进SSA。从上图可以看出，改进后的SSA在测试函数上最先收敛，且在最终收敛精度优于SSA，表明改进之后的SSA可增加种群的多样性，同时收敛速度和收敛精度均达到更优。In general, the improved SSA local search helps the SSA algorithm jump out of the local optimal solution. At the same time, this invention compares with the global optimal solution in the early stage and selects it to maintain the diversity of the population and prevent premature aggregation in the early stage. This invention selects the convergence curve of the standard test function TF1 for the original SSA and the improved SSA. The improved best point set and the definition domain of each function in the variable neighborhood search adopt the values recommended by the literature. The SSA population size is 50, and the iteration The number of times is 100. Figure 7(a) uses the original random initialization and adds the best point set to initialize the population to improve the SSA. Figure 7(b) adds the best point set to initialize the population and uses variable neighborhood search to improve the SSA. As can be seen from the above figure, the improved SSA converges first on the test function, and the final convergence accuracy is better than SSA, indicating that the improved SSA can increase the diversity of the population, while achieving better convergence speed and convergence accuracy. .
2.3外部记忆库(EM)更新策略2.3 External memory (EM) update strategy
为更好的利用每个种群在每一代进化过程中产生的非劣解的优良信息，在保证每一代产生的优秀个体不被破坏或丢弃的同时，也能保证种群的稳定性和收敛性。本发明采用独立于进化种群的外部记忆库(Extemal Memory，EM)，EM不参与种群进化，外部集中存放的是每次迭代产生解的非劣解个体部分，这使得多目标进化算法有更好的效率和有效性。In order to better utilize the excellent information of non-inferior solutions generated by each population during the evolution process of each generation, while ensuring that the excellent individuals generated in each generation are not destroyed or discarded, the stability and convergence of the population can also be ensured. This invention uses an external memory (Extemal Memory, EM) that is independent of the evolutionary population. EM does not participate in population evolution. The external centralized storage is the non-inferior solution individual part of the solution generated in each iteration, which makes the multi-objective evolutionary algorithm better. efficiency and effectiveness.
海明距离Hamming距离ρ(x，x′)＝|xx′|，表示两个编码中不同元素的个数，邻域结构N(x)可以表示为Nk(x)＝{x′|ρ(x，x′)≤ρk}。Hamming distance ρ(x, x′)=|xx′|, which represents the number of different elements in the two codes. The neighborhood structure N(x) can be expressed as Nk (x)={x′|ρ (x, x′)≤ρk }.
当新的优良个体准备插入到外部记忆库EM时，对其中中的非劣解进行快速非支配解排序，更新过程可描述为：如果新解被EM中某个非劣解所支配，比较两个个体机器层编码的Hamming距离，若ρ(x，x′)＜S/4，则不替换，若ρ(x，x′)>S/4，替换记忆库中排序等级较高的个体，S表示个体长度；如果新解支配EM中的某个解，则替换被支配的解；如果新解与EM中的非劣解没有支配关系，则将新解插入到EM中，最终EM中所有解将形成Pareto最优解集。When a new excellent individual is ready to be inserted into the external memory bank EM, the non-inferior solutions in it are quickly sorted by non-dominated solutions. The update process can be described as: If the new solution is dominated by a non-inferior solution in EM, compare the two solutions. Hamming distance of individual machine layer encoding, if ρ(x, x′)<S/4, then do not replace, if ρ(x, x′)>S/4, replace the individual with higher ranking in the memory bank, S represents the individual length; if the new solution dominates a certain solution in EM, replace the dominated solution; if the new solution has no dominance relationship with the non-inferior solution in EM, insert the new solution into EM, and finally all the solutions in EM The solutions will form the Pareto optimal solution set.
2.4Pareto解集求解多目标2.4 Pareto solution set to solve multiple objectives
多目标优化问题中多个目标间常常存在冲突，无法得到一个在所有目标上都最优的解，因此多目标优化问题求解是指求得满足所有约束得到整组目标向量的最优化。在多目标优化问题研究中，使用支配关系来表示不同解之间的优劣，若解x在任意目标下均不劣于解y且至少在一个目标下优于y，则称解x支配解y，记作x＜y。若解空间中不存在支配x的解，则称x为非支配解或者Pareto最优解。一系列Pareto最优解的集合称为Pareto最优前沿或Pareto边界。图8为Pareto最优前沿示例。在实际问题中，决策者需要从Pareto最优解集合中选择一个解作为最终决策。In multi-objective optimization problems, there are often conflicts between multiple objectives, and it is impossible to obtain a solution that is optimal for all objectives. Therefore, solving multi-objective optimization problems refers to the optimization of the entire set of objective vectors that satisfies all constraints. In the study of multi-objective optimization problems, the dominance relationship is used to express the advantages and disadvantages between different solutions. If the solution x is not inferior to the solution y under any objective and is better than the solution y under at least one objective, the solution x is said to dominate the solution y, recorded as x<y. If there is no solution that dominates x in the solution space, x is called a non-dominated solution or a Pareto optimal solution. The set of a series of Pareto optimal solutions is called the Pareto optimal front or Pareto frontier. Figure 8 shows an example of Pareto optimal front. In practical problems, the decision maker needs to select a solution from the Pareto optimal solution set as the final decision.
为了比较这些结果并获得最佳折衷方案，需要一定的机制将两个目标结合起来，因为不同的目标函数单位不同，取值范围也可能存在较大差异，研究人员经常使用模糊决策从许多不受控制的解中得到。模糊决策法首先将各目标函数标准化，使其映射到[0，1]范围内。对于一个有Q个目标函数、P组解的优化问题，其第q个目标函数、第p组解隶属度函数公式如下所示：In order to compare these results and obtain the best compromise, a certain mechanism is needed to combine the two objectives. Because different objective function units have different units, the value ranges may also have large differences. Researchers often use fuzzy decision-making from many unaffected obtained from the control solution. The fuzzy decision-making method first standardizes each objective function to map it to the range of [0, 1]. For an optimization problem with Q objective functions and P groups of solutions, the membership function formula of the q-th objective function and p-th group of solutions is as follows:
其中为Pareto最优解集中第q个目标函数的最大值、最小值。/>为第q个目标函数的第p个解；/>代表第q个目标函数第p个解的满意度。in are the maximum and minimum values of the q-th objective function in the Pareto optimal solution set. /> is the p-th solution of the q-th objective function;/> Represents the satisfaction of the p-th solution of the q-th objective function.
隶属度函数采用升半梯形函数，如图9可以直观得看出，对于最小化优化问题，当函数值小于最小值时，其隶属度为1；当函数值大于最大值时，其隶属度为0；当函数值介于最小值与最大值之间时，其隶属度在0-1之间呈线性变化。隶属度函数所计算的是第p个解到最优点fN的距离。对于本发明最小化的优化问题，越接近1，说明该解到最优点fN的距离越小，其满意度越高，这样所有的目标函数均被转化为0-1的范围，计算第p个解的满意度为：The membership function adopts a raised half-trapezoid function. As can be seen intuitively from Figure 9, for the minimization optimization problem, when the function value is less than the minimum value, the membership degree is 1; when the function value is greater than the maximum value, the membership degree is 0; when the function value is between the minimum value and the maximum value, its membership degree changes linearly between 0 and 1. What the membership function calculates is the distance from the p-th solution to the optimal point fN. For the optimization problem minimized by this invention, The closer it is to 1, the smaller the distance from the solution to the optimal point fN and the higher its satisfaction. In this way, all objective functions are converted into the range of 0-1. Calculating the satisfaction of the p-th solution is:
对于每一个非支配解，第p个解的满意度综合考虑了多个目标函数，并以满意度最低的分量的满意度值作为第p个解的满意度。满意度最高的解μ＝max{μ1，μ2，…，μP}被认为是最合适的解。For each non-dominated solution, the satisfaction of the p-th solution comprehensively considers multiple objective functions, and the satisfaction value of the component with the lowest satisfaction is used as the satisfaction of the p-th solution. The solution μ=max{μ1 , μ2 ,..., μP } with the highest satisfaction is considered to be the most appropriate solution.
2.5适应度计算2.5 Fitness calculation
根据制造执行系统数据中的工序序列，获取完工时间的方法如下所示：According to the process sequence in the manufacturing execution system data, the method of obtaining the completion time is as follows:
结合某电子离散制造企业的实际需求，某个工序在某台机器上的起始加工时间为start，加工耗时为span，加工结束时间为end。逐个将工序插入到生产队列中，具体步骤如下：Based on the actual needs of an electronic discrete manufacturing enterprise, the starting processing time of a certain process on a certain machine is start, the processing time is span, and the processing end time is end. Insert the processes into the production queue one by one. The specific steps are as follows:
1)如果对应的机器上还未加工过该工序，并且是该工件的第一道工序：1) If this process has not been processed on the corresponding machine and it is the first process of the workpiece:
·将此工序插入该机器，设置start为0，end为span。·Insert this process into the machine, set start to 0 and end to span.
2)如果对应的机器上还未加工过该工序，但该工序不是第一道工序：2) If this process has not been processed on the corresponding machine, but this process is not the first process:
·获取该工件的上一道工序的结束时间last_end。·Get the end time last_end of the previous process of the workpiece.
·设置start为last_end，end为last_end+span。·Set start to last_end and end to last_end+span.
3)如果对应的机器上已经加工过该工序：3) If the corresponding machine has already processed this process:
·在该机器上寻找一个满足条件的空闲段，条件是空闲段的时间长度不小于该工序在该机器上的生产耗时。·Find an idle segment on the machine that meets the conditions, provided that the length of the idle segment is not less than the production time of the process on the machine.
·如果该工序不是第一道工序，则还要满足空闲段的起始时间不小于该工序对应工件上一道工序的结束时间。·If this process is not the first process, it must also be satisfied that the starting time of the idle segment is not less than the end time of the previous process corresponding to the workpiece.
该离散车间在调度过程中由于原材料仓储成本、加工时间费用而导致成品存储成本大，需要计算各个工件的仓储成本：查找每台机器上的工序，当工序是该工件的最后一道工序时，根据中计算的最大完成时间和该工序的end，计算出最大提前完成时间，再乘以单位时间工件的仓储成本，得到该工件的存储成本。将所有工件的存储成本相加得到总仓储成本。During the scheduling process of this discrete workshop, the storage cost of finished products is high due to the cost of raw material storage and processing time. It is necessary to calculate the storage cost of each workpiece: find the process on each machine. When the process is the last process of the workpiece, according to Based on the maximum completion time calculated in and the end of the process, the maximum early completion time is calculated, and then multiplied by the storage cost of the workpiece per unit time to obtain the storage cost of the workpiece. Add the storage costs for all workpieces to get the total warehousing cost.
在改进后的SSA中，种群每次迭代开始时，需要对个体按照适应度进行排序。在求解多目标FJSP问题时，首先利用个体空间转换机制和解码机制得到所有个体对应的调度方案，并计算每个方案的最大完成时间和仓储成本，根据不同个体对应的最大完成时间和仓储成本值计算适应度值，通过在外部记忆库中存储非劣解并对其解进行Pareto排序，形成多个Pareto最优解集。对于每个Pareto最优解集中的解，将他们对应的方案使用模糊决策法，得出不同解的满意度，满意度越大的方案排名越靠前。In the improved SSA, at the beginning of each iteration of the population, individuals need to be sorted according to their fitness. When solving the multi-objective FJSP problem, first use the individual space conversion mechanism and decoding mechanism to obtain the scheduling plans corresponding to all individuals, and calculate the maximum completion time and warehousing cost of each plan. According to the maximum completion time and warehousing cost values corresponding to different individuals Calculate the fitness value and form multiple Pareto optimal solution sets by storing non-inferior solutions in the external memory bank and performing Pareto sorting on the solutions. For each solution in the Pareto optimal solution set, use the fuzzy decision-making method for their corresponding solutions to obtain the satisfaction of different solutions. The solution with greater satisfaction is ranked higher.
2.6流程图2.6 Flowchart
图11给出了使用改进后SSA求解多目标柔性作业车间调度FJSP问题的流程图。Figure 11 shows the flow chart of using the improved SSA to solve the multi-objective flexible job shop scheduling FJSP problem.
3、改进的SSA算法的应用方案3. Application scheme of improved SSA algorithm
生产车间是一个复杂的环境，为了提高复杂系统的稳定性，现有技术中，制造执行系统MES为五层架构，图12为制造执行系统MES的系统架构图。该架构中，数据层向下采集物理层产生的数据，向上与服务层和业务应用层进行数据交互；服务层实现如日志管理、权限管理等与具体业务无关的功能；业务应用层实现具体业务，该层与服务层的分离，可以减少对无关业务功能的处理，专注于业务的实现。MES系统可以全面的收集生产车间信息，通过调用该系统的接口，可以获取智能调度所需的生产车间信息。连续优化算法应用到车间调度问题中时，算法运行需要的部分参数要根据生产车间信息设置，因此，一个可用的车间调度算法包括算法本身和利用算法求解车间调度问题两部分。The production workshop is a complex environment. In order to improve the stability of the complex system, in the existing technology, the manufacturing execution system MES has a five-layer architecture. Figure 12 is the system architecture diagram of the manufacturing execution system MES. In this architecture, the data layer collects data generated by the physical layer downwards, and interacts with the service layer and business application layer upwards; the service layer implements functions that have nothing to do with specific businesses, such as log management and permission management; the business application layer implements specific businesses , the separation of this layer from the service layer can reduce the processing of irrelevant business functions and focus on business implementation. The MES system can comprehensively collect production workshop information. By calling the system's interface, the production workshop information required for intelligent scheduling can be obtained. When the continuous optimization algorithm is applied to the workshop scheduling problem, some parameters required for the algorithm operation must be set according to the production workshop information. Therefore, an available workshop scheduling algorithm includes the algorithm itself and the use of the algorithm to solve the workshop scheduling problem.
下面描述利用改进的SSA算法求解车间调度问题。为了实现智能调度过程，如图13将系统运行过程对数据的处理分为三部分，即信息获取与存储、数据处理和生产调度三部分。The following describes the use of the improved SSA algorithm to solve the workshop scheduling problem. In order to realize the intelligent scheduling process, as shown in Figure 13, the data processing in the system operation process is divided into three parts, namely information acquisition and storage, data processing and production scheduling.
信息获取与存储部分主要是使用信息管理模块和功能调用模块中功能进行数据的管理；The information acquisition and storage part mainly uses the functions in the information management module and function calling module to manage data;
数据处理部分主要是使用调度算法模块和信息管理模块的功能进行数据的处理以支撑生产调度的进行，对于实际的离散车间问题，需要引入基础的生产数据，每个工件的生产方式由系统的BOM信息表所决定，即工件的工序数量确定且加工顺序确定；The data processing part mainly uses the functions of the scheduling algorithm module and the information management module to process data to support production scheduling. For actual discrete workshop problems, basic production data needs to be introduced. The production method of each workpiece is determined by the system's BOM Determined by the information table, that is, the number of process steps of the workpiece is determined and the processing sequence is determined;
生产调度部分主要是在调度算法模块中使用改进的SSA算法，完成生产制造执行MES系统中的智能调度过程，提出落实到生产环境的智能调度子系统。The production scheduling part mainly uses the improved SSA algorithm in the scheduling algorithm module to complete the intelligent scheduling process in the manufacturing execution MES system, and proposes an intelligent scheduling subsystem implemented in the production environment.
总结：Summarize:
本研究提出一种基于SSA算法改进的多目标柔性车间调度方法，其包括如下步骤：This study proposes an improved multi-objective flexible workshop scheduling method based on the SSA algorithm, which includes the following steps:
步骤(1)：给出车间生产的复杂情况，抛出柔性车间调度问题，针对离散车间制造实际情况建立多目标调度优化模型；Step (1): Given the complex situation of workshop production, throw out the flexible workshop scheduling problem, and establish a multi-objective scheduling optimization model based on the actual situation of discrete workshop manufacturing;
步骤(2)：通过MSOS编码解码的方式对离散的车间调度问题进行连续化处理；Step (2): Continuously process the discrete workshop scheduling problem through MSOS encoding and decoding;
步骤(3)：改进传统的SSA算法，利用佳点集法改进初始种群位置，通过变邻域搜索算法来提高局部搜索的准确度和速度；Step (3): Improve the traditional SSA algorithm, use the best point set method to improve the initial population position, and use the variable neighborhood search algorithm to improve the accuracy and speed of local search;
步骤(4)：建立外部记忆库，使用Pareto最优解集和模糊决策法求解并获取多目标调度问题的调度序列。Step (4): Establish an external memory database, use Pareto optimal solution set and fuzzy decision-making method to solve and obtain the scheduling sequence of the multi-objective scheduling problem.
步骤(1)柔性作业车间多目标调度方法，针对生产现场提出最小最大完成时间和最小仓储成本这两个目标建立模型。Step (1) The flexible job shop multi-objective scheduling method proposes the two objectives of minimum and maximum completion time and minimum warehousing cost to establish a model for the production site.
步骤(2)编码解码的方式，对离散的车间调度问题进行连续化处理，设计了：连续空间到离散空间的转换机制：个体编码解码机制MSOS编码方式，使连续SSA优化算法可以应用到离散问题上。Step (2) The encoding and decoding method is used to continuously process the discrete workshop scheduling problem. The conversion mechanism from continuous space to discrete space is designed: the individual encoding and decoding mechanism MSOS encoding method, so that the continuous SSA optimization algorithm can be applied to discrete problems. superior.
步骤(3)改进传统的SSA算法：首先、加入佳点集使初始种群更加均匀，提升了种群多样性；然后、根据变邻域搜索算法针对SSA算法搜索的改进。Step (3) Improve the traditional SSA algorithm: first, add the best point set to make the initial population more uniform and improve the population diversity; then, improve the SSA algorithm search based on the variable neighborhood search algorithm.
改进后的SSA局部搜索共经历了两个修改过程，在迭代进行到一半前使用SSA算法进行更新位置，在这之后根据变邻域搜索算法进行搜索，其中针对车间调度问题提出3种邻域结构进行局部搜索。The improved SSA local search has gone through two modification processes. The SSA algorithm is used to update the position before half of the iteration. After that, the search is performed according to the variable neighborhood search algorithm. Three neighborhood structures are proposed for workshop scheduling problems. Perform a local search.
步骤(4)求解并获取多目标调度问题的调度序列，针对单目标优化算法SSA无法求解多目标问题：建立外部记忆库存储算法计算得到的非劣解；使用Pareto最优解集排序；并通过模糊决策法求解到多目标最优解，最终解码为最佳的调度序列。Step (4) Solve and obtain the scheduling sequence of the multi-objective scheduling problem. The single-objective optimization algorithm SSA cannot solve the multi-objective problem: establish an external memory library to store the non-inferior solutions calculated by the algorithm; use the Pareto optimal solution set to sort; and pass The fuzzy decision-making method solves the multi-objective optimal solution and finally decodes it into the optimal scheduling sequence.
将调度方法的理论成果应用于实际生产MES的智能调度子系统模块，在某电子离散制造企业设计并开发的MES系统上实现智能计划与排程，引入实际车间生产数据，设计智能调度子系统功能模块，将系统运行过程对数据的处理分为三部分，即信息获取与存储、数据处理和生产调度三部分。Apply the theoretical results of scheduling methods to the intelligent scheduling subsystem module of actual production MES, implement intelligent planning and scheduling on the MES system designed and developed by an electronic discrete manufacturing enterprise, introduce actual workshop production data, and design the functions of the intelligent scheduling subsystem The module divides the data processing during system operation into three parts, namely information acquisition and storage, data processing and production scheduling.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311365159.9ACN117634768A (en) | 2023-10-20 | 2023-10-20 | Multi-objective flexible workshop scheduling method based on improved SSA algorithm |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311365159.9ACN117634768A (en) | 2023-10-20 | 2023-10-20 | Multi-objective flexible workshop scheduling method based on improved SSA algorithm |
| Publication Number | Publication Date |
|---|---|
| CN117634768Atrue CN117634768A (en) | 2024-03-01 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202311365159.9APendingCN117634768A (en) | 2023-10-20 | 2023-10-20 | Multi-objective flexible workshop scheduling method based on improved SSA algorithm |
| Country | Link |
|---|---|
| CN (1) | CN117634768A (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118348926A (en)* | 2024-04-01 | 2024-07-16 | 重庆科技大学 | Double-layer dynamic meta heuristic method applied to multi-target flexible workshop scheduling |
| CN119941091A (en)* | 2025-04-03 | 2025-05-06 | 合肥工业大学 | Dual-objective medical waste transportation method based on improved RSA-VNS |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118348926A (en)* | 2024-04-01 | 2024-07-16 | 重庆科技大学 | Double-layer dynamic meta heuristic method applied to multi-target flexible workshop scheduling |
| CN119941091A (en)* | 2025-04-03 | 2025-05-06 | 合肥工业大学 | Dual-objective medical waste transportation method based on improved RSA-VNS |
| CN119941091B (en)* | 2025-04-03 | 2025-07-04 | 合肥工业大学 | Dual-objective medical waste transportation method based on improved RSA-VNS |
| Publication | Publication Date | Title |
|---|---|---|
| CN117634768A (en) | Multi-objective flexible workshop scheduling method based on improved SSA algorithm | |
| Kuo et al. | Application of metaheuristics-based clustering algorithm to item assignment in a synchronized zone order picking system | |
| CN115755954B (en) | Routing inspection path planning method, system, computer equipment and storage medium | |
| CN111027709B (en) | Information recommendation method and device, server and storage medium | |
| CN119045505A (en) | Large-scale unmanned aerial vehicle task planning method and system | |
| CN110751411B (en) | Cloud manufacturing task oriented manufacturing resource matching method | |
| CN109523178A (en) | A kind of O&M method and device towards power communication scene | |
| CN109086900B (en) | Electric power material guarantee and allocation platform based on multi-target particle swarm optimization algorithm | |
| Wu et al. | Analytics branching and selection for the capacitated multi-item lot sizing problem with nonidentical machines | |
| CN116307591A (en) | An optimal scheduling method for cross-basin water diversion projects based on AMOCS-PT | |
| Zhang et al. | Hierarchical multistrategy genetic algorithm for integrated process planning and scheduling | |
| CN110633784B (en) | Multi-rule artificial bee colony improvement algorithm | |
| CN115630868A (en) | Supplier selection method under external environment interference | |
| CN116523201A (en) | Flexible production unit scheduling optimization method for improving NSGA-II algorithm | |
| CN118886656A (en) | Intelligent order splitting method and system for furniture production line | |
| CN119671365A (en) | A project performance control method, device, equipment, product and storage medium | |
| CN117829545A (en) | Project fund distribution method and equipment | |
| CN113568963A (en) | Multi-target scheduling system for concurrent data integration tasks | |
| CN115270921A (en) | Power load prediction method, system and storage medium based on combined prediction model | |
| CN113988662A (en) | Emergency power supply optimal configuration method and device, electronic equipment and storage medium | |
| CN117252372B (en) | A method for resource allocation and scheduling of industrial Internet based on cluster analysis algorithm | |
| Jalalvand et al. | A multi-objective risk-averse workforce planning under uncertainty | |
| CN115374223B (en) | Intelligent blood margin identification recommendation method and system based on rules and machine learning | |
| CN116739840A (en) | Travel package recommendation method, device and storage medium based on multi-target group optimization | |
| CN117172502A (en) | Intelligent scheduling method, device, equipment and medium for aircraft maintenance personnel |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |