CN115130744A - A production scheduling method for a job shop with parallel machines under shift constraints - Google Patents

Abstract

The invention belongs to the technical field of workshop scheduling, and particularly discloses a scheduling method of a workshop with parallel machines under constraint of shift, which comprises the following steps: s1, constructing a job shop scheduling model under constraint conditions by taking the minimum lag as a target, wherein the constraint conditions comprise a shift constraint and a workpiece priority constraint; the shift constraint is as follows: one working procedure of the workpiece can only finish processing within one shift on the selected equipment, and the processing finishing time does not exceed the finishing time of the shift; the workpiece priority constraints are: all workpieces are divided into emergency groups and common groups, the emergency groups can not be delivered in an overdue mode, and the common groups can be delivered in an overdue mode; and S2, solving the job shop scheduling model according to the production information of the job shop with the parallel machine to obtain the optimal scheduling scheme of the shop. The invention can generate a better scheduling scheme according to the scheduling target, and can reasonably arrange overtime to ensure timely delivery of the emergency.

Description

A production scheduling method for a job shop with parallel machines under shift constraints

technical field

The invention belongs to the technical field of workshop scheduling, and more particularly relates to a production scheduling method for a workshop with parallel machines under shift constraints.

Background technique

Smart manufacturing is the development trend of the global manufacturing industry, and the workshop scheduling technology directly affects the efficiency and cost of manufacturing. With the wide application of multi-functional equipment such as CNC machine tools and machining centers and the rise of individualized and customized production models, flexible job shop scheduling has also become a research hotspot.

As a special kind of flexible workshop, the workshop with parallel machine widely exists in actual production. Since in the job shop scheduling problem with parallel machines, the processing time of each equipment in an equipment group may be equal, so on the equipment selection sub-problem, the algorithm for solving the classical flexible job shop scheduling problem may not be It is applicable again, so it is necessary to explore a new solution method on this basis.

In addition, in the real production workshop, the processing equipment often needs workers to operate, so it is necessary to design the worker schedule to stipulate the workers' commute time. In the assembly line, workers usually work in three shifts to ensure the continuity of the production line. However, in the flexible workshop, because there is no concept of a production line, there is no need to maintain 24-hour uninterrupted processing. Therefore, workers are usually arranged for rest time, and the production time of equipment is divided by shifts using the worker schedule, which also affects the scheduling process. great influence. Therefore, the shift constraint is a factor that must be considered in the real shop scheduling problem.

SUMMARY OF THE INVENTION

In view of the above defects or improvement needs of the prior art, the present invention provides a production scheduling method for a job shop with parallel machines under shift constraints, the purpose of which is to solve the problem of job shop scheduling with parallel machines under shift constraints. Serious problems in the long term and improve workshop production efficiency.

In order to achieve the above purpose, the present invention proposes a production scheduling method with a parallel machine workshop under shift constraints, comprising the following steps:

S1. A job shop scheduling model under constraints is constructed with the goal of minimizing delays, and the constraints include shift constraints and workpiece priority constraints;

The shift constraint is: a process of the workpiece can only be processed in one shift on the selected equipment, and the processing completion time does not exceed the end time of the shift;

The priority constraints of the workpieces are: all workpieces are divided into urgent groups and ordinary groups, the urgent group cannot be overdue for delivery, and the ordinary group can be overdue;

S2. According to the production information of the job shop with parallel machines, the job shop scheduling model is solved to obtain the best production scheduling scheme of the shop.

As a further preference, in the job shop scheduling model, the objective function f is:

The shift constraints are as follows:

S _ij ≥C _i(j-1)

B _kd ≥E _k(d-1)

The artifact priority constraints are as follows:

Among them, n represents the total number of workpieces, C _i represents the completion time of workpiece i, D _i represents the delivery date of workpiece i; S _ij represents the start processing time of the jth operation O _ij of workpiece i, and C _i(j-1) represents the completion time of the previous process of process O _ij ; B _kd represents the start time of the d-th shift of equipment k, and E _kd represents the end time of the d-th shift of equipment k.

As a further preference, the job shop scheduling model is solved by an ant colony algorithm.

As a further preference, when solving the job shop scheduling model through the ant colony algorithm, first solve the urgent group, if the urgent group is an infeasible solution, that is, there is a delay in the urgent, then the shift is replaced; and then the urgent group is solved. On the basis of , solve the common group.

As a further preference, when the shift replacement is performed, the shift replacement expectation index is used to indicate the level of the index of the expected extended time of the shift, and the shift replacement is performed accordingly; the calculation formula of the shift replacement expectation index is:

Among them, ES _kd represents the shift replacement expectation index of equipment k shift d; Etime _kdij represents how long the shift SFT _kd can be extended to meet the needs of the process O _ij when the process O _ij cannot be arranged on the shift SFT _kd ; Pstay _kdij represents if the process is extended If the time satisfies O _ij , the probability index of the operation remaining in the shift processing.

As further preferred, the concrete steps of carrying out shift replacement are as follows:

(1) Set the initial shift replacement expectation index of each shift to 0, and traverse each process in turn according to the sequence of processes in the infeasible solution;

(2) for operation O _ij , in the interval DG from the moment it can start processing to the current start moment, traverse the shifts on its currently selected processing equipment to form a set of shifts to be selected GT _ij ;

(3) For each shift in GT _ij , calculate the time Etime _kdij that needs to be extended if O _ij is processed on it; if the extended time exceeds the start time of the next shift, then Etime _kdijj is set to 0; otherwise, keep Etime _kdij , and calculate Pstay _kdij ; then obtain ES _kd of each shift in GT _ij ;

(4) Repeat steps (2) and (3) until all processes are traversed;

(5) Traverse all shifts with ES _kd greater than 0, and perform shift replacement according to the size of ES _kd ; the larger the ES _kd , the longer the selected replacement shift time; if the shifts on all working days of a device have been replaced with the longest shift If the time shift is still unable to meet the delivery time, it will be arranged to work overtime on a rest day on the weekend of the week where the shift needs to be replaced; if the weekend schedule is full, it will be postponed later;

(6) After the shift replacement is completed, if there is still a delay in the current solution, go back to step (1) for the next round of shift replacement, until a feasible solution is generated, or the current solution is abandoned after a certain number of iterations, and the end.

As a further preference, the calculation formula of the probability index Pstay _kdij is:

Among them, R is a constant greater than all STD _ij , and STD _ij is the number of days from the moment when the process O _ij can start processing.

As a further preference, after obtaining the emergency solution or the common solution, perform a local search on the current solution V _k to obtain the solution V _k '; calculate the corresponding objective function values respectively, and keep the better one of V _k ' and V _k as a solution;

The strategy of local search is: in each equipment group, randomly select a piece of equipment, and then randomly select a process on the equipment; for this process, start from the end time of the previous process of the workpiece to which it belongs, to the completion time of the process traverse the idle time period of other equipment in the equipment group; if other equipment in the group has a time period that can accommodate the process and the start time is earlier than the current equipment, the process will be adjusted to the earliest equipment that can start; If none of the selected processes has been adjusted to the processing equipment, then randomly select any process on other equipment in the equipment group where these processes are located, and exchange the processing equipment of the two processes.

As a further preference, the job shop scheduling model is solved by the nested ant colony algorithm, and the scheduling process is divided into two stages: process sorting and equipment selection. The ant colony in the process sorting stage is the large ant colony, and the ant colony in the equipment selection stage It is a small ant colony; each large ant in the large ant colony traverses the process to obtain a process sequencing plan, and the small ant colony traverses the equipment according to the plan obtained by each large ant to obtain the equipment selection plan, thus forming a complete solution. .

As a further preference, in the process sorting stage, the process with a larger ratio of processing time to shift time is preferentially arranged to be processed on the equipment; in the equipment selection stage, the equipment with the earliest start time in the same equipment group is preferentially selected.

In general, compared with the prior art, the above technical solutions conceived by the present invention mainly have the following technical advantages:

1. On the traditional job shop scheduling problem with parallel machines, the present invention considers shift constraints, and establishes a mathematical model of job shop scheduling problems with parallel machines under shift constraints with the goal of minimizing delays; Priority divides workpieces into urgent groups and common groups to avoid delays in urgent items. The invention can solve the problem of serious delay of workpieces, improve workshop production efficiency, and can reasonably arrange overtime to ensure timely delivery of urgent items.

2. The present invention combines the shift replacement rules designed by the priority of the workpieces, which can effectively carry out shift replacement, achieve the effect of arranging overtime as reasonably as possible to solve the problem of delayed delivery of urgent items, and greatly reduce the cost of breach of contract caused by the failure to deliver urgent items on time.

3. The present invention divides the scheduling problem into two stages: process sequencing and equipment selection, and is solved in stages by nested ant colony algorithm; at the same time, according to the characteristics of the problem, heuristic rules and local search strategies are designed to optimize the solution results and improve the results. Iterative efficiency.

Description of drawings

1 is a schematic diagram of a first process adjustment mode during local search according to an embodiment of the present invention;

2 is a schematic diagram of a second process adjustment mode during local search according to an embodiment of the present invention;

3 is a flowchart of a solution solution according to an embodiment of the present invention;

4 is a flowchart of solving an initial scheduling scheme based on an ant colony algorithm according to an embodiment of the present invention;

5 is a diagram of an ant travel path in a process sorting stage according to an embodiment of the present invention;

6 is a diagram of an ant travel path in a device selection stage according to an embodiment of the present invention;

FIG. 7 is a flowchart of a shift replacement rule according to an embodiment of the present invention.

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. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other as long as they do not conflict with each other.

The embodiment of the present invention provides a production scheduling method for a workshop with parallel machines under shift constraints. The basic situation of the workshop is as follows: equipment is grouped by type, there are multiple pieces of equipment in each group of equipment, and within the same equipment group, each piece of equipment The duration of the same process for processing the same workpiece is the same; the start and end times of the daily shift of the same equipment are not necessarily the same. In addition, the shifts are variable. A machine has multiple shifts, which can be replaced according to the actual production schedule, including replacing the shifts with longer ones to arrange overtime; Replaced shifts with shorter durations to reduce unnecessary working hours for workers.

The scheduling method includes the following steps:

S1. Obtain the production information of the workshop with parallel machines, including the processing time of the workpiece with scheduling, the priority of the workpiece, the processing equipment and the shift time and other data; according to the priority of the workpiece, the workpieces are divided into urgent groups and ordinary groups.

S2. Considering the priority of the workpiece, a job shop scheduling model with parallel machines under shift constraints is constructed with the goal of minimizing the delay. The job shop scheduling model is as follows:

Parameter notation:

n: total number of workpieces

m: total number of device groups

h: total number of devices

σ: the maximum number of days in the production scheduling cycle

i: workpiece serial number, i={1,2,…,n}

j: the process number of the workpiece, j={1,2,…,J _i }

w: device group number, w={1,2,…,m}

k: device number, k={1,2,…,h}

d: class number, d={1,2,…,σ}

O _ij : the jth operation of workpiece i

D _i : delivery date of workpiece i

M _ij : equipment group that can process O _ij

t _ij : machining time of process j of workpiece i

SFT _kd : the d-th shift of equipment k

B _kd : the start time of the d-th shift of equipment k

E _kd : the end time of the d-th shift of equipment k

BKP _w : candidate shift set for equipment group w

Tw : shift duration of equipment group _w

S _ij : start processing time of O _ij

C _ij : Completion time of O _ij

C _i : Completion time of workpiece i

L: a very large positive number

Decision variables:

Objective function:

Restrictions:

Among them, Equation (1) represents the objective function. In order to avoid the problem of excessive overtime, the evaluation index for the urgent group is the early completion time, and the evaluation index for the ordinary group is the delay; Equation (2) ensures that each process can only be assigned to one equipment , and can only be processed on one shift of the equipment; Equation (3) gives the definition of the completion time; Equation (4) ensures that the operation O _ij is on the unselected equipment, and the start time and completion time are 0; (5) It is stipulated that the next process can be processed only after the previous process of a workpiece is completed; Equation (6) indicates that the previous shift can be completed before the next shift can begin, and the shift periods cannot overlap; Equation (7), Equation (8) ) limits the processing period of the operation O _ij to the selected processing shift, that is, the start time cannot be before the start time of the shift, and the completion time cannot be after the end time of the shift; Equations (9) and (10) guarantee two procedures It cannot be processed on the same equipment at the same time; Equations (11) and (12) limit the value range of decision variables.

S3. Solve the job shop scheduling model according to the production information of the job shop with parallel machines. During the scheduling process, first schedule the emergency group, if there is an urgent delay, replace the shift, and then schedule the ordinary group, such as shown in Figure 3.

In this embodiment, the ant colony algorithm is preferably used to solve the problem. In each iteration, the emergency group is solved first, and then the common group is solved on the basis of the emergency group solution, and the pheromone is updated according to the solution to complete one iteration. ; and then proceed to the next iteration until the termination condition is reached, and the output at this time is the final solution, that is, the final scheduling plan. Specifically include the following steps:

S31, using the nested ant colony algorithm to solve the emergency group, as shown in Figure 4;

(1) The specific steps are:

Step 1 Initialization of the sequence sequence stage. Input the scheduling information, establish a large ant colony traversing path network according to the process information of each workpiece, initialize its pheromone table, so that the pheromone concentration on each path is equal; M large ants are scattered in any optional node.

Step 2: Path selection in the process sorting stage. The heuristic rules designed in this paper and the pheromone on the path are used to guide the ants to traverse each process.

Step 3 Initialization of the device selection phase. When the traversal of a large ant ANT is completed, according to the process sequence obtained by the large ant ANT, a small ant colony traversal path network is established, and its pheromone table is initialized so that the pheromone concentration on each path is equal, and m small ants are dispersed. on any optional device node.

Step 4. Path selection in the device selection stage. Using the heuristic rules designed in this paper and the pheromone on the path, each ant is guided to traverse the equipment in the equipment group corresponding to each process in turn.

Step 5: Calculate the amount of pheromone released in the equipment selection stage. When the traversal of a small ant is completed, a complete solution can be obtained, the solution can be evaluated, and the delay value can be calculated. Then perform a local search on the solution, compare the delay value of the previously obtained solution, keep the better one, and calculate the pheromone release amount accordingly.

Step 6: Pheromone update in device selection stage. If all the small ants reach the end point, evaporate and release pheromone for each path on the small ant colony's traversed path network; otherwise, go to Step 4.

Step 7: Calculate the amount of pheromone released in the process sequencing stage. If the small ant colony search reaches the termination condition, according to the optimal solution obtained by the small ant colony, determine the amount of pheromone released by the large ant ANT; otherwise, go to Step 4.

Step 8: The pheromone update in the process sequencing stage. If all the giant ants reach the end point, evaporate and release pheromone for each path on the traversed path of the giant ant colony; otherwise, go to Step 2.

Step 9: Determine whether the search of the large ant colony has reached the termination condition, and if so, output the optimal solution; otherwise, go to Step 2.

(2) Algorithm design

According to the characteristics of the problem, the scheduling process is divided into two stages: process sequencing and equipment selection. The two stages are solved by ant colony algorithm respectively to form a nested ant colony algorithm. The ant colony in the process sorting stage is called the large ant colony, and the ant colony in the equipment selection stage is called the small ant colony; each large ant in the large ant colony traverses the process to obtain the process sorting plan; Only the solution obtained by the big ants, traverse the equipment, obtain the optimal equipment selection scheme, form a complete solution and update the pheromone on the traversal path of the big ants, thus making the two-stage algorithm form a nested relationship.

1) Process sequencing stage

At this stage, only the processing sequence of the workpiece is determined, and the selection of equipment is not considered, so it can be regarded as a JSP problem. The algorithm process can be described as, let each ant traverse all the processes under the constraints of the process sequence of the same workpiece. Therefore, a process can be regarded as a node in the ant traversal graph. Take the 3×2 JSP problem as an example. As shown in the figure, node 0 and node 7 are virtual nodes, indicating the start and end nodes of the ant traversal. All The ant starts from node 0, traverses all process nodes, and ends at node 7. First, add the next process to be processed of all workpieces to the next traversable node set; after traversing a node, delete it from the optional node set; if the node represents the workpiece to which the process belongs and has not been processed, Then add the node of its next process to the optional node set until all nodes are traversed. When the traversal ends, the sequence of nodes traversed by the ants is a sequence of processes obtained in this cycle.

The ant chooses the next traversed node according to a pseudo-random probability as shown below:

为第k只蚂蚁在节点i时选择节点j的概率，τ_ij(t)为节点i到j的路径上信息素残余量，η_ij(t)为启发式规则，α为残余信息素的重要程度，β为启发式规则的重要程度。In the formula,

is the probability that the kth ant selects node j at node i, τ _ij (t) is the residual amount of pheromone on the path from node i to j, η _ij (t) is the heuristic rule, and α is the importance of the residual pheromone degree, β is the importance degree of the heuristic rule.

The heuristic rules for selecting the operation O _ij are:

——工序O_ij加工设备组的班次时长。In the formula,

——The shift duration of the processing equipment group in the process O _ij .

The heuristic rule determines that the closer the processing time of an operation is to the shift duration and the earlier the delivery date, the higher the probability of this operation being selected first. The process with a closer ratio of processing time to shift duration is preferred because in the same shift, if the short process is processed before the long process, there is a high probability that the long process will be processed for a long period of time after the start of processing. In this case, a time period longer than the processing time of a long process cannot be found, which makes the delay more serious.

2) Equipment selection stage

According to the workpiece sequence obtained in the previous stage, the processing equipment of each process is determined in sequence. As an example, as shown in the figure, the nodes in the figure represent devices, and the nodes in the same column represent several devices in the same device group.

Devices are numbered in the order of device groups, as shown in Table 1:

Table 1 Device No.

The basic idea of the algorithm in this stage is that each ant determines the processing equipment of each process O _ij in turn according to the determined process sequence. Each process has a corresponding equipment group M _ij , and the ants traverse each equipment in the equipment group to find the earliest time period when each equipment can be started; and then randomly select the equipment according to the probability calculated by the pseudo-random probability formula One device in the group, arrange the process O _ij on this device, that is, select one node in each column of the graph; then, traverse the device nodes of the next process; and so on, until the processing equipment is determined for all processes .

At this stage, the heuristic rules for processing equipment selection are:

This heuristic rule determines the preference for devices that can start early.

S32. After the ant traversal ends, perform a local search on the current solution V _k obtained by the emergency group to obtain the solution V _k ′. After the solution V _k ′ is obtained by local search, the objective function values corresponding to V _k ′ and V _k are calculated respectively, the better one of V _k ′ and V _k is saved, and the pheromone is updated.

The local search strategy is: in each equipment group, randomly select a piece of equipment, and then randomly select a process on this equipment. For the process, from the end time of the previous process of the workpiece to which it belongs, to the completion time of the process, traverse the idle time period of other equipment in the equipment group.

If other equipment in the group has a time period that can accommodate the process and the start time is earlier than the current equipment, the process will be adjusted to the earliest equipment that can start work. As an example, as shown in FIG. 1, for equipment group 2, process O ₂₂ on equipment M ₂₂ is randomly selected, and the idle time period from time 2 to time 8 of the first shift on equipment M ₂₁ and M ₂₃ is traversed; It is found that the process O ₂₂ can be arranged on the equipment M ₂₁ from time 6 to time 8, then the process O ₂₂ is adjusted to be processed in this time period of the equipment M ₂₁ .

If all the selected processes have not adjusted the processing equipment, randomly select any process on other equipment in the equipment group where these processes are located, and exchange the processing equipment of the two processes, as shown in Figure 2.

S33. If the current urgent group solution is an infeasible solution, it is necessary to perform shift replacement, and advance the completion time by arranging overtime, so as to convert the infeasible solution into a feasible solution to solve the problem of urgent delay. As shown in Figure 7, the shift replacement rules are as follows:

Step 1Initialization. The concept of replacing the expected index ES with the shift represents the index of the expected extended time of the shift. The ES of each shift is initialized to 0, and each process is traversed in turn according to the sequence of the processes in the infeasible solution.

Step 2: For the process O _ij , traverse the shifts on the currently selected processing equipment within the interval DG from the time when it can start processing to the current start time, and form a set of shifts to be selected GT _ij .

Step 3: For each shift in GT _ij , calculate the extended time Etime _kdij if O _ij is processed on it. If the extended time exceeds the start time of the next shift, Etime _kdijj is set to 0; otherwise, Pstay _kdij is calculated with the formula:

In the formula, R——constant, STD _ij ——the STD _ij day of the process O _ij from the time when the processing can be started. This formula indicates that the higher the shift is, the higher the probability of selecting the process O _ij after the shift is replaced.

Step 4 Calculate the shift replacement expectation index ES _kd for each shift in GT _ij . If all processes are traversed, go to Step 5; otherwise, go to Step 2 to traverse the next process. The formula for calculating ES _kd is:

Among them, ES _kd represents the replacement expectation index of equipment k shift d; Etime _kdij represents how long the shift SFT _kd can be extended to meet the needs of the process O _ij when the process O _ij cannot be arranged on the shift SFT _kd ; Pstay _kdij represents if the time is extended Satisfying O _ij , the probability index of the operation remaining in the shift processing.

Step 5 Traverse all the shifts with the expected index ES _kd greater than 0, and perform shift replacement according to the size of ES _kd . The larger the ES _kd , the longer the replacement shift duration is selected. If the shifts on all working days of a certain equipment have been replaced with the longest shifts, and the delivery time is still not met, then a rest day will be arranged on the weekend of the week where the shift needs to be replaced; , it will be postponed later.

Step 6 After the shift replacement is completed, the current solution is re-actively decoded. If there is a delay, go to Step 1 to perform the next round of shift replacement until a feasible solution is generated, or the current solution is abandoned after a certain number of iterations, and the end.

S34. On the basis of the urgent group solution, perform the ordinary group solution, and the solution method is the same as that of the urgent group; specifically, when solving the ordinary group, use the nested ant colony algorithm to solve and perform a local search, and shift replacement may not be performed.

S35. Eliminate unnecessary shift replacements. For the overall solution composed of urgent group solution and common group solution, if it is found that the pre-replacement shift can meet the production task of the current shift, such unnecessary replacement will be eliminated.

Specifically, when the urgent group is solved, shift replacement is carried out, and some unnecessary shift replacements will occur (the urgent group will not be affected after removal). The production of the group has an impact, so only shift replacements that have no impact on the urgent group and the ordinary group are excluded here.

S36. Evaluate the current solution. At this point, one iteration is completed, and according to the current solution, the total advance time of the emergency group workpiece and the total delay time of the common group are calculated, so as to update the pheromone on the ant traversal network.

S37. If the termination condition (ie the preset number of iterations) is not reached, go back to step S31 to continue the next round of iterations; otherwise, take the current solution as the optimal solution to obtain the optimal production scheduling plan for the workshop.

It must be noted that, in the above-mentioned embodiments, the methods are not necessarily executed sequentially according to the sequence number, as long as it cannot be inferred from the execution logic that the methods must be executed in a certain sequence, it means that the methods can be executed in any other possible sequence.

To sum up, at the problem level, the present invention considers the shift constraints in the traditional job shop scheduling problem with parallel machines, and aims to minimize the delay time to establish a mathematical model of the job shop scheduling problem with parallel machines under shift constraints; considering the workpiece Priority problem, divide the workpieces into urgent groups and ordinary groups according to the priority of the workpieces, and solve the problem of delaying urgent items by replacing them with reasonable shifts. At the algorithm level, the problem is divided into two stages: process sequencing and equipment selection, and nested ant colonies are designed to solve them in stages; according to the characteristics of the problem, heuristic rules and local search strategies are designed; shift replacement rules are designed to solve urgent delays question. The present invention can generate an optimal scheduling scheme according to the scheduling target, and can reasonably arrange overtime to ensure timely delivery of urgent items.

Those skilled in the art can easily understand that 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, etc., All should be included within the protection scope of the present invention.

Claims (10)

1. a production scheduling method with parallel machine workshop under a shift constraint, is characterized in that, comprises the steps: S1. A job shop scheduling model under constraints is constructed with the goal of minimizing delays, and the constraints include shift constraints and workpiece priority constraints; The shift constraint is: a process of the workpiece can only be processed in one shift on the selected equipment, and the processing completion time does not exceed the end time of the shift; The priority constraints of the workpieces are: all workpieces are divided into urgent groups and ordinary groups, the urgent group cannot be overdue for delivery, and the ordinary group can be overdue; S2. According to the production information of the job shop with parallel machines, the job shop scheduling model is solved to obtain the best production scheduling scheme of the shop. 2. the production scheduling method with parallel machine job shop under shift constraint as claimed in claim 1, it is characterized in that, in job shop scheduling model, objective function f is:

The shift constraints are as follows: S _ij ≥C _i(j-1) B _kd ≥E _k ( _d-1 ) The artifact priority constraints are as follows:

Among them, n represents the total number of workpieces, C _i represents the completion time of workpiece i, D _i represents the delivery date of workpiece i; S _ij represents the start processing time of the jth operation O _ij of workpiece i, and C _i(j-1) represents the completion time of the previous process of process O _ij ; B _kd represents the start time of the d-th shift of equipment k, and E _kd represents the end time of the d-th shift of equipment k. 3 . The production scheduling method for a job shop with parallel machines under shift constraints according to claim 2 , wherein the job shop scheduling model is solved by an ant colony algorithm. 4 . 4. The production scheduling method with parallel machine job shop under shift constraint as claimed in claim 3, it is characterized in that, when the job shop scheduling model is solved by ant colony algorithm, the urgent group is solved first, if the urgent group is solved If the solution is infeasible, that is, there is a delay in the emergency, then the shift is replaced; then, on the basis of the emergency group solution, the common group is solved. 5. The production scheduling method with parallel machine workshops under shift constraints as claimed in claim 4, characterized in that, when performing shift replacement, a shift replacement expectation index is used to represent the index level of the expected extended time of the shift, and the shift is performed accordingly. Replacement; the formula for the shift replacement expectation index is:

Among them, ES _kd represents the shift replacement expectation index of equipment k shift d; Etime _kdij represents how long the shift SFT _kd can be extended to meet the needs of the process O _ij when the process O _ij cannot be arranged on the shift SFT _kd ; Pstay _kdij represents if the process is extended If the time satisfies O _ij , the probability index of the operation remaining in the shift processing. 6. the production scheduling method with parallel machine workshop under shift constraint as claimed in claim 5, is characterized in that, the concrete steps of carrying out shift replacement are as follows: (1) Set the initial shift replacement expectation index of each shift to 0, and traverse each process in turn according to the sequence of processes in the infeasible solution; (2) for operation O _ij , in the interval DG from the moment it can start processing to the current start moment, traverse the shifts on its currently selected processing equipment to form a set of shifts to be selected GT _ij ; (3) For each shift in GT _ij , calculate the time Etime _kdij that needs to be extended if O _ij is processed on it; if the extended time exceeds the start time of the next shift, then Etime _kdijj is set to 0; otherwise, keep Etime _kdij , and calculate Pstay _kdij ; then obtain ES _kd of each shift in GT _ij ; (4) Repeat steps (2) and (3) until all processes are traversed; (5) Traverse all shifts with ES _kd greater than 0, and perform shift replacement according to the size of ES _kd ; the larger the ES _kd , the longer the selected replacement shift time; if the shifts on all working days of a device have been replaced with the longest shift If the time shift is still unable to meet the delivery time, it will be arranged to work overtime on a rest day on the weekend of the week where the shift needs to be replaced; if the weekend schedule is full, it will be postponed later; (6) After the shift replacement is completed, if there is still a delay in the current solution, go back to step (1) for the next round of shift replacement, until a feasible solution is generated, or the current solution is abandoned after a certain number of iterations, and the end. 7. the production scheduling method with parallel machine workshop under the shift constraint as claimed in claim 6, is characterized in that, the calculation formula of probability index Pstay _kdij is:

Among them, R is a constant greater than all STD _ij , and STD _ij is the number of days from the moment when the process O _ij can start processing. 8. The production scheduling method with a parallel machine job shop under shift constraints as claimed in claim 4, characterized in that, after obtaining the emergency solution or the common solution, a local search is performed on the current solution V _k to obtain the solution V _k ′ ; Calculate the corresponding objective function values respectively, and keep the better one of V _k ′ and V _k as the solution; The strategy of local search is: in each equipment group, randomly select a piece of equipment, and then randomly select a process on the equipment; for this process, start from the end time of the previous process of the workpiece to which it belongs, to the completion time of the process traverse the idle time period of other equipment in the equipment group; if other equipment in the group has a time period that can accommodate the process and the start time is earlier than the current equipment, the process will be adjusted to the earliest equipment that can start; If none of the selected processes has been adjusted to the processing equipment, then randomly select any process on other equipment in the equipment group where these processes are located, and exchange the processing equipment of the two processes. 9. The production scheduling method with parallel machine job shop under shift constraints as claimed in claim 3, wherein the job shop scheduling model is solved by nested ant colony algorithm, and the scheduling process is divided into process sequence and equipment selection In two stages, the ant colony in the process sorting stage is the large ant colony, and the ant colony in the equipment selection stage is the small ant colony; each large ant in the large ant colony traverses the process to obtain the process sorting plan, and the small ant colony is based on each ant colony. Only the solution obtained by the big ants is to traverse the equipment to obtain the equipment selection scheme, thereby forming a complete solution. 10. The production scheduling method with parallel machine workshops under shift constraints as claimed in claim 9, characterized in that, in the process sequencing stage, processes with a larger ratio of processing duration to shift duration are preferentially arranged to be processed on the equipment; In the equipment selection stage, the equipment with the earliest start time in the same equipment group is preferentially selected.

Images