CN110852500B - Resource-limited hybrid flow shop optimization method - Google Patents

Abstract

The invention relates to the field of workshop scheduling optimization. The purpose is to provide a resource-constrained mixed flow shop optimization method, the method includes: S1: Propose a discrete imperialist competition algorithm based on a two-dimensional vector encoding strategy and an adaptive local search strategy to improve the imperialist competition process; S2: Incorporating simulated annealing algorithms to improve the performance of discrete imperialist competition algorithms; S3: Dynamically allocating resources during decoding. The present invention can aim at minimizing the completion time to solve the scheduling problems of various resource-constrained mixed processes.

Description

A resource-constrained hybrid flow shop optimization method

Technical Field

The present invention relates to the field of workshop scheduling optimization, and in particular to a resource-constrained hybrid flow workshop optimization method.

Background Art

Since the resource-constrained project scheduling problem was first proposed, various resource-constrained project scheduling problems have emerged. According to the characteristics of these problems, we can classify them into several categories, such as resource-constrained parallel machine scheduling problem, resource-constrained flow shop scheduling problem, resource-constrained mixed flow shop scheduling problem, resource-constrained job shop scheduling problem, and resource-constrained flexible shop scheduling problem.

Rajkumar used a greedy randomized adaptive search procedure to solve the resource-constrained flexible job shop scheduling problem, whose goal is to minimize the maximum production time, the maximum workload, and the total workload. Zheng and Wang used a knowledge-based fruit fly optimization algorithm to solve the work order, machine, and worker allocation problem. Zhu et al. used the powerful graph database NEO4J to conduct innovative research on this problem. Gao and Pan proposed a new algorithm called the random multi-swarm micro-migratory bird optimization algorithm represented by dual vectors. Chen proposed a scheduling algorithm for the parallel machine reentrant job shop scheduling problem. Chan and Lei used genetic algorithms (GA) and variable neighborhood search, respectively, to solve this problem. Xiong et al. proposed a multi-objective evolutionary algorithm to solve this type of problem.

Mendez et al. proposed a new mixed integer linear programming mathematical model with appropriate sequence constraints for the resource-constrained process shop scheduling problem. Nishi et al. proposed a decentralized scheduling method based on Lagrangian decomposition and coordination. Figielska solved the scheduling process problem with priority and proposed a heuristic algorithm. Pei et al. proposed a hybrid BA-VNS algorithm that implemented the optimal scheduling rule in its encoding process. Lin et al. also used gas to solve this problem. Leu and Cheng et al. proposed a polynomial algorithm and considered the resource recovery process. Sural et al. proposed a complexity algorithm. Solve the unit time job scheduling problem in process workshops.

Zhang et al. adopted a global search method for resource-constrained workshop scheduling problems and designed a discrete particle swarm optimization method. Li et al. proposed a branch population genetic metaheuristic algorithm considering the dual constraints of machines and workers. Lei and Guo proposed a two-stage dynamic neighborhood search method. Tamssaouet et al. tested two algorithms and the results showed that the taboo search algorithm performed well on specific problems. Faccio proposed a simulated annealing algorithm and analyzed the sensitivity of the parameters.

Figielska proposed a column generation algorithm for the mixed flow shop scheduling problem with resource constraints, which includes linear programming, taboo search algorithm and greedy process for solving the mixed flow shop problem. Dosa et al. applied approximate algorithms and polynomial algorithms to solve parallel machine scheduling problems with job allocation constraints in different situations.

However, the above algorithms have problems such as slow solution speed, complex solution, low accuracy, etc. in practical application. The present invention aims to minimize the completion time to solve various resource-constrained hybrid process scheduling problems.

Summary of the invention

The purpose of the present invention is to solve the above-mentioned problems existing in the prior art, to provide an optimization method for the resource-constrained hybrid flow shop scheduling problem, and to shorten the completion time.

In order to achieve the above-mentioned invention object, the technical solution adopted by the present invention is: a resource-constrained hybrid flow shop optimization method, characterized in that the method comprises:

S1: A discrete imperialist competition algorithm is proposed to improve the imperialist competition process based on a two-dimensional vector encoding strategy and an adaptive local search strategy;

S2: Combine simulated annealing algorithm to improve the performance of discrete imperialist competition algorithm;

S3: Dynamically allocate resources during decoding.

Preferably, the discrete imperialist competition algorithm implementation process in S1 further includes:

Step 1 Empire initialization:

Step 2: Imperial assimilation phase;

Step 3: Empire competition stage;

Step 4: The fall of the empire.

Preferably, the encoding strategy of the discrete imperialist competition algorithm in S1 is as follows: using a two-phase encoding mechanism including two-vector-based (TVB) representations and one-machine Gantt chart (MGB) representation, where one dimension of the two vectors is a machine vector and the other dimension is a scheduling vector;

Step 1 in S1 is implemented as follows:

According to the example, the generated countries are divided into empires and colonies, and are allocated to each empire according to the power of the empire. The power of the empire is standardized according to formula (2):

C _n = c _n - max{ _ci } (2)

Among them, c _n is the fitness of the Nth empire, and C _n is the standardized power of the empire. According to the standardized power of the empire, the power of the empire is calculated using formula (3):

是帝国的总势力，P_n是一个比率，帝国的力量越大，拥有的殖民地数量就越多，最后根据公式(4)计算每个帝国的殖民地数量：

is the total power of the empire, _Pn is a ratio. The greater the power of the empire, the more colonies it has. Finally, the number of colonies of each empire is calculated according to formula (4):

NC _n =round{P _n *N _col } (4)

_NCn is the number of colonies each empire initially has, and _Ncol is the total number of colonies. Based on this number, colonies are randomly assigned to each empire, and the initialization phase for all empires and colonies is completed.

Preferably, in said S1, step 2, the empire assimilation phase, is implemented as follows:

The essence of the assimilation process is to make all colonies within an empire tend to the local optimal solution within the empire. The assimilation process is achieved by moving colonies into the empire.

The colony moves to a distance X from the empire to its new location, where X is defined as:

X～U(0,β*d) (5)

Where β is a real number greater than 1, d is the distance between the empire and the colony, and β>1 means that the colony can move toward the empire from different directions;

Add a random offset variable θ after the move to perform a wider search around the empire, θ follows a uniformly distributed random number:

θ～U(-γ,γ) (6)

Where γ is a parameter to adjust the deviation from the original direction. The values of β and γ are usually 2 and π/4 respectively. The local search strategy is as follows:

Local search strategy for the representation of a two-vector solution:

Step 1: For the machine assignment vector, we randomly select an operation and assign it to different available machines;

Step 2: For the schedule vector, we randomly use the swap and insert operators; for the swap operator, we randomly select two job numbers in the schedule vector, then swap the two jobs to generate different solutions; for the insert operator, we randomly select two jobs in the schedule vector, then delete one job and insert it in front of the other selected job;

Local search strategy for the representation of machine Gantt charts:

Step 1: Calculate the completion time of each machine in the last step;

Step 2: Find the machines with the longest completion time and store them in a vector called BM;

Step 3: Randomly select a machine B _m from BM and store all the jobs being processed by BM in a vector called BJ;

Step 4: Randomly select a job B _j in BJ, randomly select a stage j, and find the designated machine MJ that processes BJ in stage j;

Step 5: Remove job _Bj from _Mj , randomly assign _Bj to another machine in stage J, and find the best position for _Bj in the newly assigned machine.

Preferably, in said S1, step 3, the empire competition stage, is implemented as follows:

Strategy 1:

Step 1: Sort the empires by the number of colonies;

Step 2: The empire with fewer colonies is considered a weak empire, and the empire with more colonies is considered a strong empire;

Step 4: Disrupt the colonial order of weak empires;

Step 5: Randomly select selectNum colonies from the colonies of the weak empire and assign them to the strong empire;

or

Strategy 2:

Step 1: Sort the empire and its colonies by the sum of their fitness from small to large;

Step 2: The empire with high fitness is regarded as a weak empire, and the empire with low fitness is regarded as a strong empire;

Step 3: Disrupt the colonial order of weak empires;

Step 4: Randomly select selectNum colonies from the colonies of the weak empire and assign them to the strong empire;

Preferably, the S2 simulated annealing algorithm process is as follows:

Step 1: Initialize temperature;

Step 2: Create a random solution x and evaluate f(x);

Step 3: Store x in x _best ;

Step 4: When the stop condition is not met;

Step 5: Create a neighborhood solution x ^new and evaluate f(x ^new );

Step 6: The acceptance probability is P(x, x ^new ,T);

Step 7: If x is better than x _best , store x in x _best ;

Step 8: Cool down and the algorithm ends.

Preferably, in S3, the process of dynamically allocating resources is as follows:

For operation O _i,j , when calculating its start time S _i,j , we consider the following conditions: (1) the completion time of the previous stage C _i,j-1 of _Ji ; (2) the available machine time I _k ; (3) the maximum available time of the required resources of the k machines; therefore, S _i,j is calculated as follows:

是机器k所需的所有资源的最大可用时间，P_i,j为第一阶段工作的处理时间。Where A _r is the available time of resource r∈R _k ,

is the maximum available time of all resources required by machine k, and _Pi,j is the processing time of the first phase of work.

If O _i,j is the first operation of _Ji , then the start time S _i,j is calculated as follows:

After O _i,j is completed, the R _k resource will be consumed and immediately released for other operations; therefore, the available time of R _k and I _k will be updated as follows:

After all operations are scheduled, the total completion time is calculated as follows:

The beneficial effects of the present invention are mainly reflected in: being able to solve the shortest completion time and proposing the best resource optimization configuration method.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is an example diagram of a resource-constrained hybrid flow shop according to the present invention.

Figure 2 Schematic diagram of the imperial assimilation stage.

FIG3 is a schematic diagram of imperial competition in the method of the present invention.

FIG. 4 is a schematic diagram of the encoding strategy in the method of the present invention.

FIG5 is a diagram showing the parameters of the method of the present invention.

FIG. 6 is an ANOVA analysis of variance diagram of the empire competition strategy in the method of the present invention.

FIG. 7 is an ANOVA analysis of variance diagram of the best solution in the method of the present invention.

FIG. 8 is an ANOVA analysis of variance diagram of the average solution in the method of the present invention.

FIG. 9 is an ANOVA analysis of variance diagram of the worst solution in the method of the present invention.

DETAILED DESCRIPTION

The present invention will be fully described below in conjunction with embodiments:

This paper proposes a discrete imperialist competitive algorithm (D-ICA) to solve various resource-constrained hybrid process scheduling problems with the goal of minimizing the completion time. In this algorithm, we adopt two phases of encoding mechanisms: representation based on two vector solutions and representation based on machine Gantt chart solutions, and adopt a local search method. Then, D-ICA is combined with the simulated annealing algorithm (SA) to improve the performance of the algorithm. In addition, we also consider the dynamic allocation of resources during the decoding process. We tested the algorithm based on a set of randomly generated real shop scheduling system instances, and numerically analyzed and compared the algorithm with existing heuristic algorithms to verify the effectiveness of the algorithm.

1 Resource-constrained hybrid flow shop problem description

The problem under consideration can be formally described as follows. There are n jobs that require s processing stages in a certain sequence. In the whole process, there is at least one stage with two or more parallel processing machines. After the first stage is processed, the second stage continues to work. When the machine in the second stage is available, the job can be processed in the second stage, or if the first stage processing is completed, the job can be kept in the buffer space of unlimited capacity until the machine is free in the second stage. In the second stage, the job can be processed on any processor, and interruption is not allowed after the processing starts.

Between the two stages, we consider using robots to transport the work that was processed in stage 1. In addition to machines, processing work in two stages requires limited additional resources that can be shared between the stages, i.e., both stages can use a fixed amount of resources.

There are h pre-given resources in the factory, including R ₁ ,R ₂ ,...,R _h . The number of each type of resource is given in advance. The process on each machine is based on the cooperation between different types of resources. Therefore, to start the operation, it must be ensured that the machine and the resource are available at the same time. The processing intervals between conflicting operations of two resources or computers cannot overlap. The goal is to minimize the completion time.

Next, we introduce a mixed-integer linear programming model that extends the RCHFS model introduced by Li et al.

1.1 Modeling of the Resource-Constrained Hybrid Flow Shop Problem

The parameters and symbol subscripts required for RCHFS modeling are as follows:

1.2 Resource-constrained hybrid flow shop problem example

In order to solve the RCHF problem and verify the effectiveness of the D-ICA algorithm, we randomly generated 20 large-scale test cases of the RCHF problem based on actual production data. The same number of factories for each test problem was randomly generated from unidrnd(2,5). The test set of instances was divided into four categories according to the number of jobs. In order to verify the effectiveness of the D-ICA algorithm in environments with different complexity, each type of problem was divided into five sub-problems, and the number of stages of each sub-problem was different. For example, the code instance 50_2_2 means that the problem has 50 jobs, two stages, and two parallel machines in the first stage.

2 Optimization Algorithm for Solving Resource-Constrained Hybrid Flow Shop Problems

2.1 Imperialist Competition Algorithm

Inspired by the imperialist colonial competition mechanism, Gargari and Lucas proposed a new swarm intelligence optimization algorithm ICA in 2007. ICA has been widely used in some practical optimization problems. For example, Zahra et al. used ICA to solve the independent task scheduling problem in a grid environment. Compared with other algorithms, independent component analysis can find the optimal solution in a shorter time [26]. Lucas et al. designed a low-speed, single-sided linear induction motor, and the results showed that the performance of independent component analysis was better than that of genetic algorithm. Niknam et al. combined ICA with the K-means algorithm and successfully applied the hybrid method to the processing of data clusters. Recent studies have shown that ICA is an effective algorithm for solving workshop scheduling problems, such as process workshops and single-machine scheduling problems. ICA has the advantage of fast convergence speed and has proposed many improved algorithms. Bahrami et al. used chaotic mapping to determine the change of group direction in the assimilation operator. Lin et al. proposed perturbations to the ICA algorithm and replaced relatively weak imperialist countries with artificial imperialist countries to strengthen information exchange between empires.

Similar to other evolutionary algorithms, ICA starts with a set of initial solutions called the population. Each individual in the population is called a "chromosome" in genetic algorithms and a "country" in ICA. Each country is divided into two parts: the imperialist country and the colonies. Countries with better health will become empires, and countries with poorer health will become colonies of the empire. Competition between empires and stronger empires is likely to seize colonies from weaker empires. The entire competition process continues until only one empire remains, the number of algorithm iterations is reached, or the optimal solution is found. The typical independent competition process includes the establishment of the initial empire, the assimilation of colonies, competition between empires, and the disappearance of empires [36]. The algorithm flow is as follows:

(1) Initialization phase

According to the example, the generated countries are divided into empires and colonies, and are allocated to each empire according to the power of the empire. The power of the empire is standardized according to equation (2):

C _n = c _n - max{ _ci } (2)

Among them, c _n is the fitness of the Nth empire, and C _n is the standardized power of the empire. According to the standardized power of the empire, the power of the empire is calculated using formula (3):

是帝国的总势力，P_n是一个比率，帝国的力量越大，拥有的殖民地数量就越多，最后根据公式(4)计算每个帝国的殖民地数量：

is the total power of the empire, _Pn is a ratio. The greater the power of the empire, the more colonies it has. Finally, the number of colonies of each empire is calculated according to formula (4):

NC _n =round{P _n *N _col } (4)

_NCn is the number of colonies each empire initially has. Based on this number, colonies are randomly assigned to each empire. The initialization of all empires and colonies is complete.

(2) Imperial assimilation stage

The colony moves to a distance X from the empire to its new location, where X is defined as:

X～U(0,β*d) (5)

Where β is a real number greater than 1, d is the distance between the empire and the colony, and β>1 means that the colony can move toward the empire from different directions.

Add a random offset variable θ after the move to perform a wider search around the empire. θ follows a uniformly distributed random number:

θ～U(-γ,γ) (6)

Where γ is a parameter that adjusts the deviation from the original direction. The values of β and γ are usually 2 and π/4 respectively.

(3) Imperial Competition Stage:

Strategy 1:

Step 1: Sort the empires by the number of colonies.

Step 2: The empire with fewer colonies is considered a weak empire, and the empire with more colonies is considered a strong empire.

Step 4: Disrupt the colonial order of weak empires.

Step 5: Randomly select selectNum colonies from the colonies of the weak empire and assign them to the strong empire.

Strategy 2:

Step 1: Sort the empire and its colonies by the sum of their fitness from small to large.

Step 2: Those with high fitness are treated as weak empires, and those with low fitness are treated as strong empires.

Step 3: Disrupt the colonial order of weak empires.

Step 4: Randomly select selectNum colonies from the colonies of the weak empire and assign them to the strong empire.

(4) The demise of the empire:

All but the most powerful empires will collapse, and all colonies will be controlled by this unique empire. If an empire loses all its colonies, the algorithm will end when the last empire leaves or the maximum number of iterations is reached, then it will perish.

2.2 Question Coding

We use a two-phase encoding mechanism consisting of two vector-based (TVB) representations and a machine Gantt chart (MGB)-based representation. The first vector is the machine assignment vector and the second is the schedule vector. We use these two representations because in the early evolutionary stages, the two-vector-based representation can identify promising search spaces with broad search capabilities. In the later evolutionary stages, we use the machine Gantt chart-based solution representation to encode the detailed schedule of each machine and search through a sufficiently large search space.

2.3 Problem decoding

For operation O _i,j , when calculating its start time S _i,j , we consider the following conditions: (1) the completion time of the previous stage C _i,j-1 of _Ji ; (2) the available machine time I _k ; (3) the maximum available time of the required resources of the k machines. Therefore, S _i,j can be calculated as follows:

是机器k所需的所有资源的最大可用时间，P_i,j为第一阶段工作的处理时间。Where A _r is the available time of resource r∈R _k ,

is the maximum available time of all resources required by machine k, and _Pi,j is the processing time of the first stage work.

If O _i,j is the first operation of _Ji , then the start time S _i,j can be calculated as follows:

After O _i,j is completed, the R _k resource will be consumed and immediately released for other operations. Therefore, the available time of R _k and I _k will be updated as follows:

After all operations are scheduled, the total completion time is calculated as follows:

2.4 Local Search Strategy

Local search strategy for the representation of a two-vector solution:

Step 1: For the machine assignment vector, we randomly select an operation and assign it to a different available machine.

Step 2: For the schedule vector, we randomly use the swap and insert operators. For the swap operator, we randomly select two job numbers in the schedule vector and then swap the two jobs to generate different solutions. For the insert operator, we randomly select two jobs in the schedule vector and then delete one job and insert it in front of the other selected job.

Local search strategy for the representation of machine Gantt charts:

Step 1: Calculate the completion time of each machine in the last step.

Step 2: Find the machines with the longest completion time and store them in a vector called BM.

Step 3: Randomly select a machine B _m from the BM and store all the jobs being processed by the BM in a vector called BJ.

Step 4: Randomly select a job B _j in BJ, randomly select a stage j, and find the designated machine MJ that processes BJ in stage j.

Step 5: Remove job _Bj from _Mj , randomly assign _Bj to another machine in stage J, and find the best position for _Bj in the newly assigned machine.

2.5 Global Search Strategy

The SA algorithm is a stochastic optimization algorithm based on the metallurgical annealing process. Starting from a high initial temperature, the global optimal solution of the objective function is randomly searched in the solution space. That is, the local optimal solution can randomly jump out and eventually reach the global optimal solution. Similar to natural annealing, the SA solution to the optimization problem is heated, that is, randomly generated. Then, the solution is allowed to choose one of the nearby locations with a specific acceptance probability value. The acceptance probability depends on a global parameter t, namely the temperature, which decreases with the iteration of the algorithm.

即Δ＝f(x^new)-f(x)。如果采用指数冷却，有几种冷却方案。算法迭代k处的温度由公式12定义：Kirkpatrick et al. expressed the acceptance probability as a Boltzmann-like equation. In general, if the current solution is represented by x and the newly created solution is represented by x ^new , then the acceptance probability of x ^new is P(x, x ^new , T). If x ^new is better than x, then it is accepted, that is, P(x, x ^new , T); otherwise, a value randomly obtained in the interval [0, 1]. Their acceptance probability formula is the difference in fitness with x, that is,

That is, Δ = f(x ^new ) - f(x). If exponential cooling is used, there are several cooling schemes. The temperature at algorithm iteration k is defined by formula 12:

T _k = αT _k-1 = α ^k T ₀ (12)

Among them, 0<α<1 is the temperature drop rate. Obviously, the smaller α is, the slower the temperature drops.

2.6D-ICA Algorithm Framework

For the problem of optimizing the distribution path of prefabricated buildings with time windows, the designed algorithm framework is described as follows:

Step 1: Use the initialization method in Section 2.1 to generate an initial empire and assign colonies to the empire

Step 2: Empire assimilation phase, using the local search strategy mentioned in 2.4

Step 3: Empire competition phase, using the global search strategy mentioned in 2.5

Step 4: The Empire Falls

3 Experimental results and analysis

3.1 Simulation experiment parameter setting

We randomly generated 20 large-scale test cases of RCHFS problems based on real production data. The same number of factories for each test problem was randomly generated from unidrnd(2,5). The test set of instances was divided into four categories according to the number of jobs. In order to verify the effectiveness of the D-ICA algorithm in different complexity environments, each type of problem was divided into five sub-problems, and the number of stages of each sub-problem was different. For example, the code instance 50_2_2 means that the problem has 50 jobs, two stages, and two parallel machines in the first stage. We set the imperial competition selection rate to 0.2.

3.2 Analysis of simulation experiment results

To evaluate the effectiveness of the D-ica algorithm, we compared it with the artificial bee colony algorithm (abc), the discrete abc algorithm, and the multi-objective adaptive large neighborhood search algorithm.

Each algorithm was run 30 times on the same computer based on 20 test cases. The results of the comparative experiments are shown in Table 1. The instance names are shown in the first column. The second column shows the best value for each instance. The following four columns show the best values obtained by each algorithm considered in the comparison. In order to visually compare the quality of the solutions obtained by the four algorithms, we calculate the percentage deviation of the solutions and the results are shown in the last four columns.

The results shown in Table 1 can be summarized as follows: (1) the D-ica algorithm obtains 15 optimal solutions for the given example, far exceeding the other algorithms; (2) as shown in the last row, the average validity period and average percentage deviation are low. In summary, the experimental results show that D-ica is a more effective method for solving the RCHFS problem compared to other recently proposed effective algorithms. Table 1 shows the RPI values of the best solutions obtained by the four algorithms.

Table 1 Comparison of experimental results

Claims (4)

1. A resource-constrained hybrid flow shop optimization method, characterized in that the method comprises:

s1: providing a discrete empire-oriented competition algorithm for improving the empire-oriented competition process based on a coding strategy and a local search strategy of a two-dimensional vector;

s2: the performance of a discrete empire-oriented competition algorithm is improved by combining a simulated annealing algorithm;

s3: dynamically allocating resources in a decoding process;

in S3, the process of dynamically allocating resources is as follows:

for operationO _i,j At the calculation of its start time S _i,j When we consider the following conditions: (1) J is a unit of _i Last stage C _i,j-1 Completion time of (d); (2) Available machine time I _k (ii) a (3) k maximum available time of resources required by the machine; thus, S _i,j The calculation is as follows:

S _i,j ＝max(S _i,j-1 +P _i,j-1 ,I _k ,AR _k ) (7)

wherein, A _r Is that the resource R belongs to R _k The time of availability of (a) is,

is the maximum available time, P, of all resources required by machine k _i,j Processing time for the first stage operation;

if O is _i,j Is J _i First operation of (2), then start time S _i,j The calculation is as follows:

O _i,j after completion, R _k Resources will be consumed and immediately released for other operations; thus, R _k And I _k The available time of (c) will be updated as follows:

after all operations are scheduled, the total completion time is calculated as follows:

the implementation process of the discrete empire kingdom competition algorithm in the S1 further comprises the following steps:

step 1 empire initialization:

step 2, the empire assimilation stage;

step 3, an empire competition stage;

step 4, the empire and death stage;

the encoding strategy of the discrete empire-oriented competition algorithm in the S1 is as follows: using a two-phase encoding scheme comprising two-vector-based representations and a machine-Gantt-based representation, the two vectors being machine vectors in one dimension and scheduling vectors in one dimension;

the step 1 in the S1 is realized by the following steps:

according to the calculation, the generated countries are divided into empires and colonial areas and are assigned to the respective empires according to the forces of the empires, which are standardized according to the formula (2):

C _n ＝c _n -max{c _i } (2)

wherein, c _n Is the fitness of the Nth empire, C _n Is the standard strength of the empire; the force of the empire is calculated according to the empire's normalized momentum using equation (3):

is the general force of the empire, P _n Is a ratio, the larger the force of the empire, the more the number of colonial areas is owned, and finally the number of colonial areas per empire is calculated according to the formula (4):

N·C _n ＝round{P _n *N _col } (4)

N.C _.n is the number of colonial areas initially owned by each empire, N _col Based on this number, the colonial area is randomly assigned to each empire, all empires and all other empiresThe initialization phase of the colonial site is complete.

2. The resource-constrained hybrid flow shop optimization method according to claim 1, characterized in that: in the S1, the empire assimilation stage in the step 2 is realized as follows:

the essence of the assimilation process is to move all the colonists in one empire towards a locally optimal solution in the empire, which is achieved by moving the colonists into the empire

The colonial moves to the empire by a distance X to a new location, X being defined as:

X～U(0,β*d) (5)

where β is a real number greater than 1, d is the distance between the empire and the colonial ground, β > 1 indicating that the colonial ground can move towards the empire from different directions;

a random offset variable theta is added after the move to perform a more extensive search around the empire, theta obeying uniformly distributed random numbers:

θ～U(-γ,γ) (6)

wherein gamma is a parameter for adjusting deviation from the original direction, and values of beta and gamma are respectively 2 and pi/4;

the local search strategy is as follows:

local search strategy for representation of two vector solutions:

step 1: for machine allocation vectors, we randomly choose one operation and allocate it to different available machines;

and 2, step: for scheduling vectors, we use swap and insert operators randomly; for the swap operator, we randomly select two job numbers in the scheduling vector, and then swap the two jobs to generate different solutions; for insert operators, we randomly select two jobs in the scheduling vector, then delete one job and insert it in front of the other selected job;

local search strategy for a representation of a machine gantt chart:

step 1: calculating the completion time of each machine in the last step;

and 2, step: finding the machines with the longest completion time and storing them in a vector called BM;

and step 3: randomly selecting a machine B from BM _m And all jobs that the BM is handling are stored in a vector named BJ;

and 4, step 4: randomly selecting one job B in BJ _j Randomly selecting a stage j, and finding a designated machine MJ for processing the BJ in the stage j;

and 5: from M _j Delete in operation B _j Randomly assigning B _j To another machine in the J stage, and find B in the newly allocated machine _j The optimum position of (a).

3. The resource-constrained hybrid flow shop optimization method according to claim 2, characterized in that: in the S1, the imperial competition stage in the step 3 is realized as follows:

the first strategy is as follows:

step 1: sorting empires according to the number of colonial areas;

step 2: the empire with less colonial land is used as a weak empire, and the empire with more colonial land is used as a strong empire;

and 4, step 4: disturbing the colonial place sequence of the small and weak empires;

and 5: randomly selecting selectNum breeding places from breeding places of a weak empire state to belong to a strong empire state;

or

And (2) strategy two:

step 1, sorting according to the fitness sum of the empire and the colonial place from small to large;

step 2: the large adaptability is used as a weak empire and the small adaptability is used as a strong empire;

and 3, step 3: disturbing the colonial place sequence of the small and weak empires;

and 4, step 4: selectNum colonial places are randomly selected from colonial places of the weak empire to belong to the strong empire.

4. The resource-constrained hybrid flow shop optimization method according to claim 3, characterized in that: the S2 simulated annealing algorithm process is as follows:

step 1: initializing temperature;

and 2, step: creating a stochastic solution x and evaluating f (x);

and step 3: store x in x _best Lining;

and 4, step 4: when the stop condition is not satisfied;

and 5: creating a neighborhood solution x ^new And evaluating f (x) ^new )；

And 6: the acceptance probability is P (x, x) ^new ,T)；

And 7: if x is better than x _best Store x in x _best ；

And 8: and (5) cooling, and ending the algorithm.

Images