CN106971235A - A kind of flexible job shop Optimization Scheduling in batches that there is intermediate storage constraint - Google Patents

Abstract

The invention discloses a kind of flexible job shop Optimization Scheduling in batches that there is intermediate storage constraint, belong to Job-Shop technical field.Including setting up flexible job shop Optimal Scheduling model and initiation parameter；Consider the limited constraints of intermediate storage warehouse amount of storage；Different types of work-piece batch machining path is any；Different types of workpiece is carried out in batches, to determine its batch splitting scheme；Each work-piece batch is with random sequence according to the production equipment in its preference probability selection each process；Equipment selects the sub- batch of suitable workpiece to be processed also according to its preference probability from its wait batch queue；Until completing batch number is equal to lot count, this scheduling scheme is obtained；Computing is iterated, optimal scheduling method is exported.By the above-mentioned means, the present invention can greatly improve utilization rate of equipment and installations, shorten the whole production cycle, improve production efficiency, realize flexible job shop Optimized Operation in batches.

Description

Flexible job shop batch optimization scheduling method with intermediate storage constraint

Technical Field

The invention belongs to the field of workshop scheduling, and particularly relates to a batch optimization scheduling method for a flexible job workshop with intermediate storage constraint.

Background

In the beginning of the twentieth century, an industrial prototype has just been formed, the market demand for products is relatively single, and manufacturing enterprises begin to adopt a large-batch and few-variety rigid automatic flow production line to produce products in order to meet the market demand, improve the production efficiency and save the manufacturing cost. However, in the middle and late 60 s, with the rapid development of global economy and science and technology, consumers are no longer satisfied with a single type of product, and the demand for the product is increasingly diversified, and the product is expected to have bright features and styles while the product is required to have higher quality and shorter production period. In order to meet the demands of consumers and accelerate the updating of products, manufacturers strive to change the current production state and try to establish a new production mode which is suitable for various products, small batch and customizable features.

In a modeling enterprise, the production of products usually needs a plurality of processes to be completed, each process generally has a plurality of processing machines, and an intermediate warehouse is generally arranged between adjacent processes for storing intermediate products so as to ensure the continuity of the production of each process. In the conventional flow shop scheduling problem, it is generally assumed that the storage capacity between adjacent processes is infinite, but in the actual industrial production process, the situation that the storage capacity of an intermediate warehouse is limited needs to be considered.

Because the essence of the production scheduling problem is the problem of combinatorial optimization, if a single part is taken as an independent individual during scheduling and participates in sequencing optimization, the scale of the scheduling problem becomes large, and the algorithm cannot be accepted in both storage space and calculation space. Therefore, the batch contained in the workpiece needs to be divided into a plurality of sub-batches, and the sub-batches are taken as dispatching units. This type of batch ordering optimization problem, called the Lot optimization problem (Lot optimization), which divides a workpiece into sub-batches, was first proposed by Reiter in 1966. The method relates to batch division and sequencing optimization, is more complex than the traditional scheduling problem, is more close to actual production, and is suitable for the production characteristics of multiple varieties and small batches.

Thus, a flexible job shop batch optimization scheduling problem considering intermediate warehousing constraints arises. The different types of lot processing paths in such scheduling problems are arbitrary, but the number of steps included and the order of the steps are predetermined. The scheduling needs to solve the problems that batching is carried out under the constraint condition that the storage amount of the intermediate warehouse is limited, the batch dividing scheme of various workpieces is determined, machine resources are distributed to each procedure of each sub-batch, and the optimal processing sequence of each sub-batch on a processing machine is determined so as to meet the scheduling target.

At present, only a few scholars at home and abroad deeply research the batch optimization scheduling problem of the flexible job shop with intermediate storage constraint. Khosla builds a two-stage flow shop scheduling problem with limited intermediate storage as a mixed integer linear programming model, and provides two lower bounds and several heuristic algorithms of the problem based on the model. Nowicki proposes an efficient tabu search algorithm to solve the flow shop scheduling problem with intermediate stored permutation ordering aimed at minimizing makespan (the maximum completion time for all workpieces). And the Tang and the Xuan establish the problem as a static discrete time integer programming model by using a modeling strategy that the intermediate storage is taken as a parallel machine with the processing time of 0, and provide an effective Lagrangian relaxation algorithm. Pan Korea and Zhu Jianying aim at optimizing the production period, the starting preparation time is considered, the batch optimization scheduling problem of the flexible job workshop is researched, equal division is carried out according to the minimum processing batch, and the processing sequence is determined by optimization of a genetic algorithm. In Sunzhige et al, a batch algorithm and a sequencing algorithm based on a genetic algorithm are proposed, the number of the sub-batches of each workpiece is optimized, and the batch of each sub-batch is determined by adopting an equal sub-batch dividing strategy. And considering production batch and starting preparation time, under the condition of a given batch scheme, combining a heuristic assignment rule and a simulated annealing algorithm, and providing a hybrid genetic algorithm for solving the Job-shop flexible scheduling problem under the Makespan performance index. Under the condition of giving the number of the sub-batches, adopting a consistent sub-batch division strategy to provide a three-stage algorithm consisting of pre-division, tabu search algorithm optimization processing sequencing and sub-batch adjustment to solve the Job-shop batch optimization scheduling problem. The method is characterized in that a uniform sublot division strategy is adopted by the Baijunjie and the like, a multi-target flexible batch optimization scheduling problem is solved through a particle swarm algorithm, and a vernier-based method is designed to realize batch division. Huang R.H. discusses the multi-target Job-shop scheduling problem under four conditions that batch workpieces are divided into 1, 2, 3 and 4 equal sub-batches respectively, and the ant colony algorithm is adopted for sequencing optimization.

Most of the existing researches are focused on the scheduling problem of the flow shop with storage constraint, and most of the existing batch methods are carried out under the condition that the number of the sub-batches or the size of the sub-batches is manually determined in advance, and further researches on batch division schemes are not carried out. The invention researches the batch optimization scheduling problem of the flexible job workshop under the condition of considering the limited storage resources, combines the batch optimization and the batch scheduling, and provides a dynamic batch algorithm and a flexible scheduling algorithm of a single batch.

Disclosure of Invention

Aiming at the defects in the prior art, the invention aims to provide a batch optimization scheduling method for a flexible job shop with intermediate storage constraint, which takes equipment, batches and an intermediate warehouse in the workpiece production process as independent integers under the condition of considering the limited storage resources, and each part executes corresponding behaviors according to corresponding rules and combines batch optimization and batch scheduling, thereby greatly improving the equipment utilization rate and shortening the processing period.

In order to achieve the purpose, the invention adopts the technical scheme that:

a batch optimization scheduling method for a flexible job shop with intermediate storage constraint is characterized by comprising the following steps: the individual sub-batches of the same type of workpiece need not be joined for processing, allowing the machine to insert other types of sub-batches between the individual sub-batch tasks that process one type of workpiece. And optimizing and determining a batch division scheme of the workpiece batches under the condition of considering the constraint that the number of the intermediate warehouse bins and the storage capacity are limited, allocating machine resources for each process of each sub-batch, determining the optimal processing sequence of each sub-batch and minimizing the maximum completion time.

Establishing a mathematical model of the following flexible job shop optimization scheduling problem:

min Z＝C_max(1)

R_s≤R_max(4)

R_s＝R_o+R_r(6)

formula (1) is the objective function, C_maxRepresents a maximum completion time; equation (2) represents a calculation method of the maximum completion time of the entire machining process, in which: BN_nmIs a machine u_mBatch size, pt, of the upper batch n_nmFor batch n in machine u_mThe processing time of (1), N being the total number of batches; the formula (3) is a batch division constraint, which indicates that the total batch sum of the same workpiece distributed to each parallel machine is not changed when batch division is carried out, and the total batch sum is kept as the initial processing batch size of the workpiece; equation (4) indicates that the number of bins of the intermediate warehouse corresponding to each production level is limited; the total length of the workpieces stored in each bin is less than or equal to the length of the bin, and L is_RIs the length of the bin; equation (6) indicates that the bin number remains unchanged.

Each lot of workpieces may be processed by its own processing tool for each process and entered into its lot task waiting queue according to its own criteria and standards. Each tool may select a lot from the lot task wait queue for processing. After each working procedure, the sub-batches of the workpieces can become final products, and if the sub-batches of the workpieces are the final products, the finished products directly enter a finished product warehouse; otherwise, applying for warehouse space resources from the intermediate warehouse, and after obtaining the resources, continuing to perform the processing of the subsequent procedures until the intermediate warehouse space resources become final products. And the intermediate warehouse allocates bin resources according to the resource allocation standard, and recovers the allocated resources after the tasks corresponding to the processing batches are completed.

The selection of which processing tool to select from the candidate tools for a workpiece lot is primarily related to the tool state of the tool and the processing power of the tool for the lot. The state of the device is defined as:

wherein: x_m(t) ∈ {0,1} is time t device u_mAvailability of 1, unavailable of 0; the effect of 1 in the denominator is to convert mu_m(t) is limited to a value range of [0,1 ]]；Q_m(t) time t device u_mThe number of batches in the waiting queue; n is_kIs a device u_mThe lot number of the kth lot in the waiting queue of (1);is u_mThe last kth lot is executed for the required processing time,is u_mThe time required for switching the upper k-1 th batch to the k batches.

To achieve a reasonable selection of a lot to a device, the preference probability of a lot to a device can be expressed as:

wherein,_m∈ {0,1} denotes u_mWhether the lot can be processedα is used to balance the current equipment status of the equipment and the relative importance of the equipment to the processing capacity of the batch in the process of equipment selection, and the values can be determined according to experience or simulation experiments, JA_nsA collection of devices capable of processing the batch.

In order to realize the reasonable selection of the batch by the equipment, a corresponding preference selection strategy is defined:

selection strategy 1: a lot having a long processing time is preferably selected. That is, in a flow line production, workpieces with longer total processing times on all machines should receive a higher processing priority than workpieces with shorter total processing times.

Selection strategy 2: in the case of sufficient bins, batches to be intermediate products are preferably selected.

In the batch partitioning problem, the sub-batch is in a U-shaped relationship with the production cycle. When the batch size of the sub-batches is too large, the load balance among machines is not facilitated; when the number of lots is too small, the number of lots may be too large, which may increase the time for adjusting lots of the machine between lots and increase the number of times tasks are transferred between processes. Therefore, the reasonable batching scheme is the guarantee of realizing the optimized scheduling and finishing the overall scheduling target. Based on the scheduling objective of minimizing the maximum completion time, several batch scheduling rules are defined:

rule 1: the processing equipment runs at full load as much as possible, and the characteristics of the processing equipment are exerted.

Rule 2: the processing equipment is arranged for the batch, and the batch switching time is minimized as much as possible.

Rule 3: the processing equipment is arranged for the batch, and the batch completion time is earliest as much as possible.

Rule 4: unnecessary idle time is reduced as much as possible in the equipment processing process.

Suppose that a processing path, denoted P, is formed by selecting one device from each of the parallel batch processing devices of each production stage in the production order_lAnd l is a processing path number. Note N_lminFor processing a path P_lThe minimum of the storage of a single bin of all intermediate warehouses. The batch optimization algorithm is thus constructed with the following steps:

step 1: defining a predetermined queue for each device, initializing the predetermined queue to be empty, and completing the queue at a time

Step 2: randomly selecting a BN_pq>0 initial workpiece lot. The selected workpiece batch selects one device step by step according to the formula (2) to form a processing path p_lAnd calculate

And step 3: selected initial batch divisionBatch, the batch size of each sublot beingIf it isGo to step 5; otherwise go to step 4.

And 4, step 4: will remainThe workpieces being respectively allocated to the frontIn each sub-batch.

And 5: updating the selected processing path p_lA predefined queue completion time of the device.

Step 6: if BN is present_pq>0(p＝1,2,…,NS；q＝1,2,…,n_p) Turning to step 2; otherwise, ending.

Based on an optimization selection strategy and a batch optimization algorithm, allocating machine resources for each procedure of each sublot and determining the optimal processing sequence of each sublot, and giving a batch optimization scheduling algorithm flow of the flexible job shop as follows:

step 1: and (5) initializing. Setting the current optimal target value to be + ∞, and giving cycle timesAnd taking values of all empirical parameters, initializing the attributes and states of all parts in the optimization model, setting the current time to be 0, defining an equipment response time matrix, setting the equipment response time of all equipment to be + ∞, setting the number of all warehousing occupied resources to be 0 and setting the number of finished batches to be 0.

Step 2: and (3) carrying out batch operation on various workpieces according to the algorithm 1 to obtain different types of workpiece sub-batches.

And step 3: selecting equipment on each production level according to preference probability of all the workpiece sub-batches obtained in the step 2 in a random sequence, arriving at a waiting batch sequence of the equipment, updating the state of the selected equipment, and setting response time as the completion time of a process on the currently executed and selected workpiece sub-batch; if the first process is the first process, the response time is set as the time when the currently executed selected workpiece batch enters the dispatching environment.

And 4, step 4: the equipment executes the processing behaviors according to the response time sequence, and if no workpiece sub-batch is processed on the equipment, the step 5 is directly carried out; otherwise, the current processing batch is finished and the equipment state is updated, the response time is set as the completion time of the sub-batch, and the step 6 is carried out.

And 5: and (4) selecting the equipment selected in the step (4), and selecting a proper workpiece sub-batch from the waiting batch queue for processing according to the preference probability. If so, setting the response time of the batch as the completion time of the selected batch; if the batch task waiting queue is not selected and is not empty, the equipment response time of the equipment is set to the minimum value of the completion time of the last working procedure of all the sub-batches in the batch task waiting queue.

Step 6: if the workpiece batch becomes a final product after the procedure is finished, directly entering a finished product warehouse, releasing warehouse space resources corresponding to equipment of the previous procedure, adding 1 to the number of finished batches, and turning to the step 8; otherwise, applying for warehouse space resources from the corresponding intermediate warehouse, and setting the application quantity asGo to step 7.

And 7: if R is_r≥R_a(R_r＝R_s-R_oWherein R is_sThe total number of warehouse positions on the production level s; r_oThe number of occupied resources in the warehouse on the production level s), the workpieces corresponding to the batch are respectively stored into different bin positions according to different types, and the step 8 is carried out; otherwise, stopping the machine and waiting.

And 8: if the number of the finished batches is equal to the total number of the batches, comparing the scheduling result with the current optimal scheduling result, if the scheduling result is superior to the current optimal scheduling result, saving the scheduling result as the optimal scheduling result, and otherwise, keeping the current optimal scheduling result unchanged.

And step 9: re-initializing each part state and equipment response time and number of completed batches,if it is notGo to step 3, otherwise execute step 10.

Step 10: and outputting the optimal scheduling result and the Gantt chart, and ending the algorithm.

The beneficial results of the invention are:

aiming at the characteristics of the processing process of the flexible job shop, the flexible idea is introduced into the field of scheduling research of the flexible job shop, the flexible scheduling method is provided, batch optimization and batch scheduling are combined, the fast solving speed is achieved, the better optimizing performance is achieved, the equipment utilization rate is greatly improved, and the whole production period is shortened. The method is flexible and high in expandability, and has good application prospect and popularization value in the field of solving the problem of complex scheduling in the multi-stage batch processing process.

Drawings

FIG. 1 is a flow chart of a scheduling method of the present invention.

FIG. 2 is a Gantt chart of flexible scheduling for glass deep processing according to an embodiment of the present invention.

Detailed Description

The present invention will be described in detail below with reference to the accompanying drawings and specific embodiments. The present embodiment is implemented on the premise of the technical solution of the present invention, and a detailed implementation manner and a specific operation process are given, but the scope of the present invention is not limited to the following embodiments.

Referring to fig. 1, a flexible job shop batch optimization scheduling method with intermediate storage constraint includes the following specific implementation steps:

step 1: establishing a mathematical model of the following flexible job shop optimization scheduling problem:

min Z＝C_max(1)

R_s≤R_max(4)

R_s＝R_o+R_r(6)

formula (1) is the objective function, C_maxRepresents a maximum completion time; equation (2) represents a calculation method of the maximum completion time of the entire machining process, in which: BN_nmIs a machine u_mBatch size, pt, of the upper batch n_nmFor batch n in machine u_mThe processing time of (1), N being the total number of batches; the formula (3) is a batch division constraint, which indicates that the total batch sum of the same workpiece distributed to each parallel machine is not changed when batch division is carried out, and the total batch sum is kept as the initial processing batch size of the workpiece; equation (4) indicates that the number of bins of the intermediate warehouse corresponding to each production level is limited; the total length of the workpieces stored in each bin is less than or equal to the length of the bin, and L is_RIs the length of the bin; equation (6) indicates that the bin number remains unchanged.

Step 2: and (5) initializing. Setting the current optimal target value to be + ∞, and giving cycle timesAnd taking values of all empirical parameters, initializing the attributes and states of all parts in the optimization model, setting the current time to be 0, defining an equipment response time matrix, setting the equipment response time of all equipment to be + ∞, setting the number of all warehousing occupied resources to be 0 and setting the number of finished batches to be 0.

And step 3: all original slice initial batches select cutting machines according to preference probabilities in a random sequence, arrive at a waiting batch queue of equipment, the selected cutting machines update states, and response time is set as time for entering a dispatching environment of the currently executed and selected original slice initial batches. The batch-to-equipment preference probability may be expressed as:

wherein,_m∈ {0,1} denotes u_mα is used to balance the current equipment status of the equipment and the relative importance of the equipment's processing capacity for the batch during equipment selection, and its value can be determined empirically or by simulation experiments_nsA collection of devices capable of processing the batch.

The device state is determined by the following equation:

wherein: x_m(t) ∈ {0,1} is time t device u_mAvailability of 1, unavailable of 0; the effect of 1 in the denominator is to convert mu_m(t) is limited to a value range of [0,1 ]]；Q_m(t) time t device u_mThe number of batches in the waiting queue; n is_kIs a device u_mThe lot number of the kth lot in the waiting queue of (1);is u_mThe last kth lot is executed for the required processing time,is u_mThe time required for switching the upper k-1 th batch to the k batches.

And 4, step 4: the cutting machine processes according to the response time sequence, if no original sheet initial batch is processed on the cutting machine, the step 5 is directly carried out; otherwise, the current processing batch is finished, the equipment state is updated, the response time is set as the finishing time of the original sheet initial batch, and the step 6 is carried out.

And 5: and (4) selecting the cutting machine selected in the step (4), and selecting a proper original sheet initial batch from the waiting batch queue according to the preference selection strategy to process. If so, setting the response time of the batch as the completion time of the selected batch; and if the batch task waiting queue is not selected and is not empty, setting the equipment response time of the cutting machine as the minimum value of all batches put into production in the batch task waiting queue. Go to step 4. The preference selection policy of the device for the batch is as follows:

selection strategy 1: a lot having a long processing time is preferably selected. That is, in a flow line production, workpieces with longer total processing times on all machines should receive a higher processing priority than workpieces with shorter total processing times.

Selection strategy 2: in the case of sufficient bins, batches to be intermediate products are preferably selected.

Step 6: if the glass single sheets generated after the original sheet initial batch cutting are the final products, directly entering a finished product warehouse, adding 1 to the number of batches, and turning to the step 14; otherwise, applying for warehouse space resources from the corresponding intermediate warehouse, and setting the application quantity as

And 7: if R is_r≥R_a(R_r＝R_s-R_oWherein R is_sThe total number of warehouse positions on the production level s; r_oThe number of occupied resources in storage on the production level s), storing the glass single sheets corresponding to the original sheet initial batch into different storage spaces according to different types, and turning to the step 8; otherwise, stopping the machine and waiting.

And 8: and carrying out batch operation on each single sheet initial batch to obtain different types of single sheet sub-batches. Before considering the constraint of limited bin number and storage capacity of the intermediate binAnd optimizing and determining a batch dividing scheme of the glass single sheets. Suppose that a processing path, denoted P, is formed by selecting one device from each of the parallel batch processing devices of each production stage in the production order_lAnd l is a processing path number. Note N_lminFor processing a path P_lThe minimum of the storage of a single bin of all intermediate warehouses. The batch optimization algorithm for each single-chip initial batch was thus constructed with the following steps:

step 8.1: defining a predetermined queue for each device, initializing the predetermined queue to be empty, and completing the queue at a time

Step 8.2: randomly selecting a BN_pq>0 initial monolithic batch. The selected single chip batch selects one device step by step according to the formula (2) to form a processing path p_lAnd calculate

Step 8.3: selected initial batch divisionBatch, the batch size of each sublot beingIf it isGo to step 8.5; otherwise go to step 8.4.

Step 8.4: will remainThe workpieces being respectively allocated to the frontIn each sub-batch.

Step 8.5: updating the selected processing path p_lA predefined queue completion time of the device.

Step 8.6: if BN is present_pq>0(p＝1,2,…,NS；q＝1,2,…,n_p) Go to step 8.2 for the single slice batch; otherwise, ending.

And step 9: and 8, selecting equipment on the next production level according to the preference probability of all the single-chip sub-batches obtained in the step 8 in a random sequence, arriving at a waiting batch sequence of the equipment, updating the state of the selected equipment, and setting the response time as the completion time of the last process of the currently executed and selected single-chip sub-batch.

Step 10: the equipment executes the processing behaviors according to the response time sequence, and if no single-chip sub-batch is processed on the equipment, the step 11 is directly carried out; otherwise, the current processing batch is completed and the equipment state is updated, the response time is set as the completion time of the sub-batch, and the step 12 is carried out.

Step 11: and (4) selecting the selected equipment in the step (10), and selecting a proper single-chip sub-batch from the waiting batch queue for processing according to the preference probability. If so, setting the response time of the batch as the completion time of the selected batch; if the batch task waiting queue is not selected and is not empty, the equipment response time of the equipment is set to be the minimum value of the completion time of the last working procedure of all the single-chip sub-batches in the batch task waiting queue.

Step 12: if the glass single sheets become final products after the procedure is finished, directly entering a finished product warehouse, releasing warehouse space resources corresponding to equipment in the previous procedure, adding 1 to the number of finished batches, and turning to the step 14; otherwise, applying for warehouse space resources to the next-level warehouse. Go to step 13.

Step 13: if R is_rIf not less than 1, the single sub-batch enters the warehouse and the step 9 is carried out; otherwise, stopping the machine and waiting.

Step 14: if the number of the finished batches is equal to the total number of the batches, comparing the scheduling result with the current optimal scheduling result, if the scheduling result is superior to the current optimal scheduling result, saving the scheduling result as the optimal scheduling result, and otherwise, keeping the current optimal scheduling result unchanged.

Step 15: re-initializing each part state and equipment response time and number of completed batches,if it is notGo to step 3, otherwise execute step 16.

Step 16: and outputting the optimal scheduling result and the Gantt chart, and ending the algorithm.

Examples

A certain glass deep processing manufacturing workshop takes 1 order task and contains 5 original sheet initial batches. Production stage 1 was equipped with four cutters, and the processing capacity and processing time of each cutter are shown in tables 1 and 2.

TABLE 1 cutting machine processing capability table (mm)

TABLE 2 cutting machine processing time (Single batch processing time)

Indicating that the cutting machine is not able to process the blank

Four types of individual sheets are produced after each initial batch of sheets is cut in this example. The different processing machines represent different processing operations, each of which has one or more parallel machines. The glass deep processing process mainly comprises edging, cleaning, toughening, coating and hollowing. The workshop is provided with two edging machines, two cleaning machines and two coating machines, and one toughening furnace and one hollow machine respectively. The dimensions of each individual piece and the processing time thereof are shown in Table 3, and a machine processing time of 0 indicates that the glass corresponding to the original lot does not pass through the process. The processing time of the tempering procedure is single batch processing time, and the processing procedure time of the other procedures is single-sheet processing time. Table 4 shows the intermediate warehouse bin sizes at each level.

TABLE 3 processing time

TABLE 4 intermediate warehouse bin size (mm)

The parameters are set as follows: number of cyclesα - β -1, the example of the dispatching method of the present invention is used for example verification, machine selection, processing sequence and batch distribution of each batch of glass are shown as a Gantt chart of glass deep processing flexible dispatching, i.e. fig. 2 shows, the box on each equipment in the drawing represents the batch being processed, the number 1 in the box represents the first original sheet initial batch, 11 represents the first sublot of the first type of glass sheet generated by the initial batch 1, 12 represents the 2 nd batch of the first type of glass sheet generated by the initial batch 1, the rest of the numbers are analogized in turn, and the number above the box represents the processing time of the glass sublot.

Claims (5)

1. A flexible job shop batch optimization scheduling method with intermediate storage constraints is characterized by comprising the following steps:

step 1: establishing a mathematical model of the following flexible job shop optimization scheduling problem:

min Z＝c_max(1)

$C_{\max }=\underset{1\≤m\≤M}{\max }\underset{n=1}{\overset{N}{\Σ}}({\mathrm{BN}}_{nm}*{\mathrm{pt}}_{nm})---\left(2\right)$

$\underset{m=1}{\overset{M_s}{\Σ}}{\mathrm{BN}}_{nm}={\mathrm{BN}}_{pq}---\left(3\right)$

R_s≤R_max(4)

$\underset{n=1}{\overset{{\mathrm{BN}}_{nm}}{\Σ}}{L}_n\≤L_R---\left(5\right)$

R_s＝R_o+R_r(6)

formula (1) is the objective function, C_maxRepresents a maximum completion time; equation (2) represents a calculation method of the maximum completion time of the entire machining process, in which: BN_nmIs a machine u_mBatch size, pt, of the upper batch n_nmFor batch n in machine u_mThe processing time of (1), N being the total number of batches; the formula (3) is a batch division constraint, which indicates that the total batch sum of the same workpiece distributed to each parallel machine is not changed when batch division is carried out, and the total batch sum is kept as the initial processing batch size of the workpiece; equation (4) indicates that the number of bins of the intermediate warehouse corresponding to each production level is limited; the total length of the workpieces stored in each bin is less than or equal to the length of the bin, and L is_RIs the length of the bin; the formula (6) indicates that the bin number is kept constant;

step 2: initializing, setting the current optimal target value to be + ∞, and giving cycle timesAnd each empirical parameter value, initializing the attribute and state of all parts in the optimization model, setting the current time to be 0, defining an equipment response time matrix, setting the equipment response time of all equipment to be + ∞, setting the number of all warehousing occupied resources to be 0 and setting the number of completed batches to be 0;

and step 3: carrying out batch operation on each workpiece batch to obtain different types of workpiece sub-batches;

and 4, step 4: selecting equipment on each production level according to the preference probability of all the sub-batches obtained in the step 3 in a random sequence, arriving at a waiting batch sequence of the equipment, updating the state of the selected equipment, and setting the response time as the completion time of a process on the currently executed and selected workpiece sub-batch; if the first procedure is adopted, the response time is set as the time for the currently executed and selected workpiece batch to enter the dispatching environment;

and 5: the equipment executes the processing behaviors according to the response time sequence, and if no workpiece sub-batch is processed on the equipment, the step 6 is directly carried out; otherwise, the current processing batch is finished and the equipment state is updated, the response time is set as the completion time of the sub-batch, and the step 7 is carried out;

step 6: selecting the equipment selected in the step 5, and selecting a proper sub-batch from the waiting batch queue for processing according to the preference probability; if so, setting the response time of the batch as the completion time of the selected batch; if the batch task waiting queue is not selected and is not empty, setting the equipment response time of the equipment as the minimum value of the completion time of the last process of all the sub-batches in the batch task waiting queue;

and 7: if the workpiece batch becomes a final product after the procedure is finished, directly entering a finished product warehouse, releasing warehouse space resources corresponding to equipment of the previous procedure, adding 1 to the number of finished batches, and turning to the step 9; otherwise, applying for warehouse space resources from the corresponding intermediate warehouse, and setting the application quantity asTurning to step 8;

and 8: if R is_r≥R_aWherein R is_r＝R_s-R_o，R_sTotal number of bins stocked in production level s, R_oIf the number of occupied resources in the warehouse on the production level s is large, the workpieces corresponding to the batch are respectively stored into different bins according to different types, and the step 9 is carried out; otherwise, stopping the machine and waiting;

and step 9: if the number of the finished batches is equal to the total number of the batches, comparing the scheduling result with the current optimal scheduling result, if the scheduling result is superior to the current optimal scheduling result, saving the scheduling result as the optimal scheduling result, otherwise, keeping the current optimal scheduling result unchanged;

step 10: re-initializing each part state and equipment response time and number of completed batches,if it is notGo to step 4, otherwise execute step 11;

step 11: and outputting the optimal scheduling result and the Gantt chart, and ending the algorithm.

2. The flexible job shop batch optimization scheduling method with intermediate storage constraints according to claim 1, wherein the batch partitioning scheme of the workpieces is determined by optimization under the constraint of considering the limited number of intermediate warehouse positions and storage capacity; suppose that a processing path, denoted P, is formed by selecting one device from each of the parallel batch processing devices of each production stage in the production order_lL is the processing route number, and is recorded with N_lminFor processing a path P_lThe minimum of the storage of a single bin of all intermediate warehouses above, thus constructing a batch optimization algorithm for each single-chip initial batch as follows:

step 1: defining a predetermined queue for each device, initializing the predetermined queue to be empty, and completing the queue at a time

Step 2: randomly selecting a BN_pq>0, selecting one device step by step according to the formula (2) to form a processing path P_lAnd calculate

And step 3: selected initial batch divisionBatch, the batch size of each sublot beingIf it isGo to step 5; otherwise, turning to the step 4;

and 4, step 4: will remainThe workpieces being respectively allocated to the frontIn each sub-batch;

and 5: updating the selected processing path P_lA predefined queue completion time for the device;

step 6: if BN is present_pq>0(p＝1,2,…,NS；q＝1,2,…,n_p) Turning to step 2; otherwise, ending.

3. The flexible job shop batch optimization scheduling method with intermediate storage constraints as claimed in claim 1, wherein to achieve a reasonable lot-to-equipment selection, the lot-to-equipment preference probability is expressed as:

$p\left(u_m\right)=\frac{{\mathrm{\δ}}_m{\left({\mathrm{\μ}}_m\right)}^{\∂}{(1/{\mathrm{pt}}_{nm})}^{\mathrm{\β}}}{\underset{u_{m^{,}}\∈{\mathrm{JA}}_{ns}}{\Σ}{\mathrm{\δ}}_{m^{,}}{\left({\mathrm{\μ}}_{m^{,}}\right)}^{\∂}{(1/{\mathrm{pt}}_{{\mathrm{nm}}^{,}})}^{\mathrm{\β}}}$

wherein,_m∈ {0,1} denotes u_mα is used to balance the current equipment status of the equipment and the relative importance of the equipment's processing capacity for the batch during equipment selection, and its value is determined empirically or by simulation experiments_nsA collection of devices capable of processing the batch.

4. The flexible job shop batch optimization scheduling method with intermediate storage constraints according to claim 3, wherein the equipment status is determined by the following formula:

${\mathrm{\μ}}_m\left(t\right)=\frac{X_m\left(t\right)}{1+{\mathrm{pt}}_{n_{1}m}+\underset{k=2}{\overset{Q_m\left(t\right)}{\Σ}}({\mathrm{\τ}}_{n_{k-1}{n}_{k}m}+{\mathrm{pt}}_{n_{k}m})}$

wherein: x_m(t) ∈ {0,1} is time t device u_mAvailability of 1, unavailable of 0; the effect of 1 in the denominator is to convert mu_m(t) Is limited to [0,1 ]]；Q_m(t) time t device u_mThe number of batches in the waiting queue; n is_kIs a device u_mThe lot number of the kth lot in the waiting queue of (1);is u_mThe last kth lot is executed for the required processing time,is u_mThe time required for switching the upper k-1 th batch to the k batches.

5. The flexible job shop batch optimization scheduling method with intermediate storage constraints of claim 1 wherein the equipment to batch preference selection policy is:

selection strategy 1: preferentially selecting batches with long processing time, namely, workpieces with longer total processing time on all machines in the flow line production should obtain higher processing priority than workpieces with shorter total processing time;

selection strategy 2: in the case of sufficient bins, batches to be intermediate products are preferably selected.