CN114839930A - Integrated dispatching system for distributed assembly blocking flow workshop - Google Patents

Abstract

The invention relates to the technical field of distributed production scheduling in modern intelligent manufacturing, in particular to an integrated scheduling system for a distributed assembly blocking flow workshop, which comprises the following steps: constructing a processing sequence of the workpieces in each workshop in the distributed assembly blocking flow water workshop according to rules extracted from the problems, wherein the sequence is used for representing the processing technological process of the workpieces; a self-learning heuristic selection strategy is designed, and the historical success rate of each low-level heuristic is summarized into knowledge for guiding the selection of the subsequent low-level heuristic; a low-level heuristic for adjusting the workpiece sequence is designed; the beneficial effects are as follows: the invention defines an integer programming model of the problem of the distributed assembly blocking flow water workshop, quantitatively expresses rules extracted from the scheduling problem of the distributed blocking flow water workshop and constructs a high-quality initial workpiece sequence.

Description

An integrated scheduling system for distributed assembly blocking flow workshop

technical field

The invention relates to the technical field of distributed production scheduling in modern intelligent manufacturing, in particular to an integrated scheduling system for distributed assembly blocking flow workshops.

Background technique

Manufacturing is the main body of the national economy, the foundation of a country, and the foundation of a strong country. At a time when the world is undergoing profound changes unseen in a century, the deep integration of advanced technologies such as the Internet of Things, cloud computing, big data, and artificial intelligence with manufacturing is driving major changes in the industry. Therefore, efficient production scheduling optimization methods and reasonable scheduling strategies are the keys for manufacturing enterprises to improve their core competitiveness in the production process.

Scheduling problems exist widely in real problems, such as aviation scheduling, logistics distribution, transportation, manufacturing, power system, network communication and so on. The problem of scheduling research is to reasonably allocate resources to each part of a decomposable task under certain constraints, so as to obtain the optimal performance index. Production scheduling refers to arranging the resources, processing time and processing sequence used by its various components to optimize one or more production goals under the constraints of process routes, resource conditions, and delivery dates as much as possible. There are many complexities in the production scheduling problem. For example, the mathematical model is difficult to establish or the established model is inaccurate. As the scale of the problem increases, the computational complexity of the solution space increases exponentially, and the algorithm used cannot solve the problem in polynomial time. The optimal solution, as well as the complex processing environment, there are many uncertain factors. Traditional methods such as mathematical methods can obtain accurate solutions for small-scale problems, but when solving large-scale problems, they cannot obtain optimal solutions within an acceptable time (polynomial time) range. Therefore, finding an optimization method that is suitable for large-scale problems and does not depend on specific problems is the key to solving the production scheduling problem. The research shows that the intelligent optimization method has the advantages of fast solution speed, strong versatility, and does not depend on the problem itself, and can obtain a satisfactory solution with high accuracy through limited iteration, which largely overcomes the shortcomings of traditional methods. Scholars have extensively studied and applied it to the flow shop scheduling problem.

Hyperheuristic algorithm is a general solution framework that adaptively selects an optimizer to solve complex problems. It has the characteristics of simple framework and few algorithm parameters. The hyperheuristic framework consists of two layers, including a high-level control strategy and a set of low-level heuristics at the bottom. High-level control strategies include heuristic selection mechanisms and acceptance criteria for solutions. The operation mechanism of the super heuristic is to start from an initial solution, select a suitable low-level heuristic according to the heuristic selection mechanism, and then apply the heuristic to the current solution to generate a candidate solution, and decide whether to accept the candidate solution according to the receiving mechanism of the solution. Finally, the selection probability of each low-level heuristic is updated through the feedback information. The hyper-heuristic algorithm is not limited by the specific problem. Since the high-level control strategy is well isolated from the bottom-level heuristic, the designer will focus on the design of the control strategy. For different optimization problems, it is a more reasonable and efficient solution to analyze the characteristics of the nature of the problem, obtain knowledge to guide effective search, avoid invalid search, and then design a knowledge-driven hyper-heuristic algorithm. Therefore, using the hyperheuristic algorithm to solve the distributed blocking flow shop scheduling problem has certain research basis and advantages.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a kind of integrated scheduling system for distributed assembly blocking flow shop, using a self-learning super-heuristic algorithm (SLHH) to minimize the total amount of assembly products in view of the problems existing in the prior art. Total tardiness (TTD) is the goal to solve the distributed assembly blocking flow shop scheduling problem. The algorithm can optimize the operation efficiency and performance of the distributed assembly blocking flow shop scheduling system.

In order to achieve the above object, the present invention provides the following technical solutions:

An integrated scheduling system for distributed assembly blocking flow workshop, characterized in that it comprises the following steps:

Step 1: According to the rules extracted from the problem, construct the processing sequence of the workpieces in each workshop in the distributed assembly blocking flow workshop, and the sequence is used to represent the processing process of the workpiece;

Step 2: A self-learning heuristic selection strategy is designed, which summarizes the historical success rate of each low-level heuristic into knowledge, which is used to guide the selection of subsequent low-level heuristics;

Step 3: A low-level heuristic for adjusting the artifact sequence is designed.

Preferably, in step 1, according to the sorting of the total processing time of each workpiece, in the distributed blocking flow workshop, with the optimization goal of minimizing the total flow time of the assembled products, the processing sequence in each processing workshop is constructed and generated.

Preferably, in step 2, according to the processing sequence in each factory provided in step 1, combined with the workpiece composition of each product, the time to start assembly, and the time consuming of the assembly process, in the assembly factory, in order to minimize the total amount of assembled products Elapsed time is an optimization objective to construct an assembly sequence in an assembly shop.

Preferably, in step 3, a distributed assembly blocking flow shop scheduling sequence is generated according to the processing sequence and assembly sequence generated in the above-mentioned steps 1 and 2, so that the maximum flow time of the assembled product is optimized.

A computer-readable storage medium contains a computer program, which, when processed by a CPU, can implement the method steps provided by a distributed assembly blocking flow shop integrated scheduling system based on a knowledge-driven method.

Compared with the prior art, the beneficial effects of the present invention are:

(1) The present invention defines an integer programming model for the distributed assembly blocking flow shop problem, quantitatively expresses the rules extracted from the distributed blocking flow shop scheduling problem, and constructs a high-quality initial workpiece sequence.

(2) Using a heuristic selection strategy based on self-learning, the historical success rate of each heuristic is summarized as knowledge, which is used to guide the algorithm for self-learning heuristic selection.

(3) Different low-level heuristics can effectively adjust the workpiece sequence of machining workpieces and obtain a satisfactory scheduling sequence.

(4) The present invention is simple in logic, easy to implement and easy to expand, and the integrated system can be easily extended to solve other scheduling problems in the field of intelligent manufacturing production.

Description of drawings

Fig. 1 is the schematic diagram of rule 1;

Fig. 2 is the schematic diagram of rule 2;

Fig. 3 is the schematic diagram of rule 3;

Fig. 4 is the schematic diagram of workpiece allocation principle NRa;

Fig. 5 is algorithm flow chart;

6 is a schematic diagram based on key plant insertion operations;

Figure 7 is a schematic diagram based on key plant switching operations.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

Example 1

An integrated scheduling system for distributed assembly blocking flow workshop, comprising the following steps:

Step 1: According to the rules extracted from the problem, construct the processing sequence of the workpieces in each workshop in the distributed assembly blocking flow workshop, which is used to represent the processing process of the workpiece; In the blocking flow shop, the optimization goal is to minimize the total flow time of the assembled product, and the processing sequence in each processing shop is constructed.

Step 2: A self-learning heuristic selection strategy is designed, which summarizes the historical success rate of each low-level heuristic into knowledge, which is used to guide the selection of subsequent low-level heuristics; The processing sequence, combined with the workpiece composition of each product, the start time of assembly, and the time-consuming of the assembly process, in the assembly factory, the optimization goal is to minimize the total flow time of the assembled products, and the assembly sequence in the assembly workshop is constructed.

Step 3: A low-level heuristic for adjusting the workpiece sequence is designed; according to the processing sequence and assembly sequence generated in the above steps 1 and 2, a distributed assembly blocking flow shop scheduling sequence is generated, so that the maximum flow time of the assembled product is optimized.

A computer-readable storage medium contains a computer program, which, when processed by a CPU, can implement the method steps provided by a distributed assembly blocking flow shop integrated scheduling system based on a knowledge-driven method.

Example 2

Analyzing the properties of the problem is a necessary condition for constructing efficient algorithms using the problem rules. Therefore, the properties of the distributed assembly blocking flow shop scheduling problem are explored, in which the final product sequence consists of the production process of the workpiece and the assembly process of the product. Decide. And, as soon as all workpieces of the same product have been machined in the processing plant, the assembly process of the product begins immediately. Inspired by the above characteristics, three kinds of rules are extracted from the distributed assembly blocking flow shop scheduling problem, and the representation of the rules is given:

Rule 1 states that in each processing plant, all the workpieces of the same product should be distributed together for processing, so that the start of assembly time of the product is as early as possible, and the quantitative expression is as follows:

If the workpiece Ju belonging to the product P _h is at the kth position of the factory f, the binary variables x _{u , k, f} take 1; if the workpiece J _v belonging to the product P _h is at the k+1th position of the factory f, the binary The variables x v, _{k +1, f} take 1, that is to say, the workpieces Ju and J _v belonging to the product _Ph are assigned to be processed together. The schematic diagram of rule 1 is shown in Figure 1.

Rule 2 states that the assembly process begins as soon as all workpieces belonging to the same product have been machined in the processing plant. The quantification is expressed as follows:

J _P = {J _P (1), J _P (2), ..., J _P (h), ..., J _P (S)}

表示产品的装配序列，

表示第h个组装的产品。规则2的示意图如图2所示。Among them, J _P represents the workpiece set of the last processed workpiece belonging to all products, and _IP (h) represents the last processed workpiece belonging to the product P _h .

represents the assembly sequence of the product,

Represents the hth assembled product. A schematic diagram of Rule 2 is shown in Figure 2.

Rule 3 indicates that the workpieces belonging to the same product should be assigned to different factories for parallel processing, which helps to advance the start assembly time of the product, and the quantitative expression is as follows:

表示在工厂f中属于产品P_h的工件数目，n_h是组成产品P_h的工件数目，规则3 的示意图如图3所示。in,

represents the number of workpieces belonging to product P _h in factory f, n _h is the number of workpieces composing product P _h , and the schematic diagram of rule 3 is shown in Figure 3.

In the distributed assembly blocking flow shop scheduling problem, the scheduling of workpieces in the processing stage is largely affected by the assembly stage. In order to start the assembly phase as early as possible, three kinds of rules are used to construct an efficient scheduling sequence. First, products are sorted in descending order based on the total machining time of all workpieces belonging to the same product. Then, according to the total processing time of each workpiece, the workpieces of the same product are sorted in descending order. Second, the workpieces are assigned to various processing plants for processing. The assignment rules of workpieces are as follows: select the first f workpieces in the initial workpiece sequence, and assign them to the first position of each factory in turn. Second, according to the NRa rule, the remaining workpieces are distributed to all processing plants.

The NRa rule is shown in Figure 4. That is, the workpieces are taken out from the unscheduled workpiece sequence in turn, and the position with the smallest total flow time is selected for insertion. A special case needs to be considered when calculating the total elapsed time. Since the workpieces are sequentially assigned to the factory, the number of workpieces that make up the product may not be complete when calculating the assembly completion time. Therefore, the completion time of the last machined workpiece belonging to the current product is regarded as the start assembly time of the product. The construction heuristic is shown in Algorithm1.

In the SLHH algorithm, a heuristic selection mechanism is used to select the LLH. For the heuristic selection mechanism, the historical success rate of each LLH is summarized as knowledge to guide the algorithm for heuristic selection. First, the selection probability of each LLH is initialized to an infinite positive number to ensure that every low-level heuristic can be selected. Therefore, it is necessary to translate historical success rates into knowledge that guides low-level heuristic self-learning choices. The description formula of knowledge is as follows:

sr _g (LLH _i )=sn _g (LLH _i )/t _g (LLH _i )

where t _g (LLH _i ) represents the running time of the ith low-level heuristic acting on the scheduling sequence of LLH in the past g iterations, sr _g (LLH _i ) is the knowledge, and ss _g (LLH _i ) represents the selection probability . In general, if the quality of the solution improves, the selectivity of LLH increases. The heuristic selection mechanism is described in Algorithm 2.

Adopting the probability-based acceptance criterion to accept potential poor solutions helps to avoid the algorithm from falling into local optimum, thus ensuring the diversity of search. The algorithm of the receiving mechanism is shown in Algorithm 3.

According to the factory allocation rules in the initialization phase, the generated artifact sequence is allocated to the various factories. The initial solution is constructed by rules extracted from the distributed assembly blocking flow shop scheduling problem. In the heuristic selection mechanism, the selected low-level heuristic is applied to the current solution to generate a new solution. Then, the local search strategy is used to improve the search ability of the algorithm. The selection of the entire low-level heuristic is an online learning process, with each step making decisions based on the state of the solution. For the receiving criterion, the inferior solution is received with a certain probability to avoid the algorithm falling into the local optimum. The flowchart of the SLHH algorithm is shown in Figure 5.

When facing specific problems, the design of low-level heuristics also has an important impact on the super-heuristic algorithm, so seven low-level heuristics are designed in this system. The low-level heuristics are introduced below:

LLH ₁ : Randomly select a workpiece from any factory, and then tentatively insert the workpiece into all positions in all factories, and the position with the smallest total flow time is the insertion position of the workpiece.

LLH ₂ : Randomly select multiple workpieces and remove them from different factories, then tentatively insert these workpieces into all positions in all factories in turn, and select the best positions to insert these workpieces into each factory in turn.

LLH ₃ : For each factory, each workpiece of the factory is taken out in turn, and inserted into all positions of the factory, and the best position is selected to insert the removed workpiece into the factory.

LLH ₄ : For each factory, swap the positions of adjacent workpieces in that factory in turn to find the best position.

LLH ₅ : Take out the workpieces in the key factory in turn, then insert them into all the positions of the non-critical factories, find the best position and insert the removed workpieces into other factories, the operation process is shown in Figure 6.

LLH6: Swap the positions of all workpieces in the critical factory and non-critical factory in turn to find the best position. The operation process is shown in Figure 7.

LLH ₆ : Variable neighborhood descent method, the operation process is shown in Algorithm 4.

The above are only preferred embodiments of the present invention and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention shall be included in the protection scope of the present invention. Inside.

Claims (5)

1. an integrated scheduling system for distributed assembly blocking flow shop, is characterized in that, comprises the steps: Step 1: According to the rules extracted from the problem, construct the processing sequence of the workpieces in each workshop in the distributed assembly blocking flow workshop, and the sequence is used to represent the processing process of the workpiece; Step 2: A self-learning heuristic selection strategy is designed, which summarizes the historical success rate of each low-level heuristic into knowledge, which is used to guide the selection of subsequent low-level heuristics; Step 3: A low-level heuristic for adjusting the artifact sequence is designed. 2. a kind of integrated scheduling system for distributed assembly blocking flow shop according to claim 1, it is characterized in that: in step 1, according to the sorting of the total processing time of each workpiece, in the distributed blocking flow shop, with Minimizing the total transit time of the assembled product is the optimization goal, and the configuration generates the machining sequence in each machining shop. 3. A kind of integrated scheduling system for distributed assembly blocking flow shop according to claim 1, it is characterized in that: in step 2, according to the processing sequence in each factory provided in step 1, combine each product's processing sequence. The workpiece composition, the time to start assembly, and the time-consuming assembly process. In the assembly plant, the assembly sequence in the assembly workshop is constructed with the optimization goal of minimizing the total flow time of the assembled product. 4. a kind of integrated scheduling system for distributed assembly blocking flow shop according to claim 1, is characterized in that: in step 3, according to the processing sequence and assembling sequence produced in above-mentioned step 1 and step 2, generate distribution The assembly blocking flow shop scheduling sequence makes the maximum flow time of the assembled products optimal. 5. A computer-readable storage medium containing a computer program which, when processed by a CPU, can implement the method steps provided in claim 1.

Images