CN111382941B - A Parallel Task Scheduling Method with Multiple Constraints - Google Patents

Abstract

The invention discloses a parallel task scheduling method with multiple constraints, comprising the following steps: 1. Initialization process: setting a feature number for each parallel task, constructing a number pool of candidate decoding code strings, and setting an initial feasible solution range of the candidate solutions ; 2. Repeat the optimization process: use the number pool and the feasible solution range to generate multiple candidate decoding code strings; calculate the fitness value of each code string, if the iteration termination condition is met, the candidate decoding code with the best fitness value will be Otherwise, the distribution model of the candidate decoding strings is grouped, and the feasible solution range of each group of encoding strings is calculated; new candidate decoding strings are generated from the feasible solution range, and then the optimization process is repeated. The invention adopts the strategy of group optimization and self-adaptive adjustment of the search range, and can search for the optimal scheduling scheme in a very short time.

Description

A Parallel Task Scheduling Method with Multiple Constraints

technical field

The invention relates to a parallel task scheduling method with multiple constraints, and belongs to the technical field of production scheduling.

Background technique

Production scheduling is the work of arranging the process execution process and personnel assignment according to certain production operation conditions. A reasonable scheduling scheme can efficiently allocate production labor and improve work efficiency.

Since the production scheduling problem is a kind of NP-Hard, it is not suitable for traditional optimization techniques to solve. In order to effectively solve the production scheduling problem, the patents with the application numbers CN201610281979.3, CN201710866667.3 and CN201710965924.9 respectively adopt the evolutionary algorithm, the improved empire competition algorithm and the firefly algorithm to realize the task scheduling of the flexible workshop; the application number is CN201710013045.6 And the patent of CN201610628188.3 adopts genetic algorithm to realize assembly process optimization and Codelet scheduling respectively. These production scheduling methods centered on intelligent optimization algorithms have a large amount of calculation and a long time for optimization, and often experience the phenomenon of "premature convergence". Therefore, improving the optimization performance and optimization speed of the production scheduling process has practical significance for production practice.

SUMMARY OF THE INVENTION

The purpose of the present invention is to overcome the deficiencies in the prior art, and to provide a fast production scheduling method with simple method and excellent performance for a class of parallel task scheduling problems with constraints.

To achieve the above object, the present invention adopts the following technical solutions to realize:

A parallel task scheduling method with multiple constraints, comprising the following steps:

Step A, set the feature number for each parallel task, form the number pool of the candidate decoding code string; Set the initial feasible solution range;

Step B, randomly generate a plurality of candidate decoding strings according to the feasible solution range and the number pool, and calculate the fitness value of the candidate decoding strings;

Step C, judge whether the optimization termination condition is satisfied according to the fitness value, then take the candidate decoding string with the highest fitness value as the optimal scheduling scheme, and end the iterative process; otherwise, perform step D;

Step D, according to the fitness value of the candidate decoding string, divide the candidate decoding string into several groups, and calculate the distribution model of each group of candidate decoding strings respectively;

Step E: Grouping and calculating the feasible solution range of the candidate decoded code string according to the distribution model, and then going to step B.

Further, the method for generating the candidate decoding string includes the following steps:

Select a code bit of the candidate decoded code string, and randomly select a range of feature numbers from the number pool according to the feasible solution range of the code bit and put it on the code bit. If no feature number that satisfies the feasible solution range is found , then select the feature number closest to the range and put it on the code bit until all the code bits are placed with the feature number, and the obtained code string at this time is the generated candidate decoding code string.

Further, the composition of the numbering pool includes the following steps:

All numbers of the numbering pool consist of feature numbers of parallel tasks, and the number of feature numbers is equal to the number of respective subtasks.

Further, the feasible solution range of the candidate decoding string is determined by the following methods:

Suppose the center of gravity of the kth coded bit of the candidate decoding string is a _k , then the feasible solution range of the coded bit is [ _ak -σ _k a _k +σ _k ], where σ _k is the standard deviation of the kth coded bit , if the range exceeds the permitted range of the feature number, it will be replaced by the permitted range of the feature number.

Further, the calculation of the fitness value of the candidate decoded string includes the following steps:

Assuming the final end time of the parallel task is T, its fitness value is 1/T; if the current candidate solution does not meet the preset constraints, a penalty mechanism is enabled: the fitness value is reduced by more than two times.

Further, the constraints include:

1) Each subtask in the same task meets the requirements of the sequence of execution and the length of time for completion;

2) The subtasks between different parallel tasks meet the sequence requirements of execution sequence;

3) The total number of people completing parallel tasks and the number of people participating in subtasks meet the quota requirements.

Compared with the prior art, the beneficial effects achieved by the multi-constraint parallel task scheduling method provided by the present invention include: adopting the strategy of candidate solution grouping search, improving the diversity of candidate solutions, and avoiding premature iteration process Stop; by dynamically calculating the feasible solution range of the candidate decoding code string, the self-adaptive ability of problem solving is improved, and the optimization speed is accelerated.

Description of drawings

FIG. 1 is a flowchart of a parallel task scheduling method with multiple constraints provided by an embodiment of the present invention.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings. The following examples are only used to illustrate the technical solutions of the present invention more clearly, and cannot be used to limit the protection scope of the present invention.

Assuming that a scheduling task consists of four parallel tasks, the preset completion time (unit: minutes) and number of participants of each subtask are shown in Table 1. The total number of people performing the task is 5. The subtasks in the same task are executed according to the sequence number, and it is required that subtask 3 of task A must end before subtask 2 of task B; the candidate solution scale is 27, divided into three groups, each with 9 candidate solutions; the duration of the minimum makepan is 5 times.

Table 1 The preset time of the scheduling task and the number of participants

Step 1. Set the necessary parameters.

According to the problem description and Table 1, determine the necessary parameters of task scheduling.

Step 2: Construct the number pool and set the initial feasible solution range.

According to the parallel task numbers, set the feature numbers of the four tasks as 1, 2, 3, and 4. Knowing the number of subtasks of the four parallel tasks, the number pool can be expressed as:

X={1,1,1,1,1,2,2,2,2,3,4,4,4,4}

Since the value range of the feature number is between 1 and 4, the initial range of feasible solutions for each coded bit of the candidate decoding string is set to [1 4].

Step 3, generate initial candidate solutions.

Table 2 is the randomly generated 9 candidate decoding strings. For example, candidate solution 1 can be expressed as:

x1={24412214412113}

Table 2 9 candidate decoding strings

encoding position 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Candidate solution 1 2 4 4 1 2 2 1 4 4 1 2 1 1 3 Candidate solution 2 4 1 2 1 4 2 1 1 2 3 4 4 1 2 Candidate solution 3 2 2 2 4 1 1 4 4 1 4 1 3 2 1 Candidate solution 4 4 4 3 1 1 1 1 4 2 1 2 2 2 4 Candidate solution 5 2 1 3 4 4 2 2 1 1 1 1 2 4 4 Candidate solution 6 1 1 4 4 1 4 2 1 1 2 2 4 2 3 Candidate Solution 7 4 3 2 2 1 1 2 1 1 1 2 4 4 4 Candidate solution 8 1 4 2 4 1 2 3 2 4 2 4 1 1 1 Candidate solution 9 1 1 4 4 1 2 4 4 1 2 3 2 2 1

Step 4, calculate the completion time and fitness value of parallel tasks

Taking the encoded string x1 of the candidate solution 1 as an example, the calculation process of the completion time of the parallel task and the fitness value of the candidate solution is described.

Since in the candidate decoding string, each subtask in the same task adopts the same feature number, in order to identify the subtask, the following provisions are made: the order in which the same feature code appears in the candidate decoding string represents the serial number of the subtask. Table 3 shows the correspondence between the encoded string bits of the candidate solution 1 and the subtasks of each task.

Table 3 Correspondence between coding bits and subtasks of candidate solution 1

code bits subtask 1 subtask 2 subtask 3 subtask 4 subtask 5 task A 4 7 10 12 13 task B 1 5 6 11 task C 14 task D 2 3 8 9

In the following, according to the sequence from left to right of the candidate decoding code string x1, the start time of each subtask and the number of people waiting for work are calculated bit by bit (as shown in Table 4).

The first sub-task of task B and task D requires two people to participate, and the current total number of people is 5, so these two sub-tasks can be started at the same time, and the number of people waiting for the job is 1 at this time.

According to the completion time of subtask 1 of task D, the subtask will be completed in 5 minutes. When sub-task 1 of task D is over, the number of people waiting to be posted is 3. According to the sequence of the code string, subtask 2 of task D needs to be arranged. Since the number of people required for this subtask is 2, subtask 2 of task D can be arranged immediately. At this time, the number of people waiting for work is 1.

Subtask 1 of task A requires 5 people to participate. Therefore, although subtask 2 of task D ends at the 10th minute, there are only 3 people waiting for work at this time, and the total number of people waiting for work must wait for subtask 1 of task B to end. 5-people. In this way, the start time of subtask 1 of task A is calculated from the end time of subtask 1 of task B, and the number of people waiting for work is 0 at this time.

Subtasks 2 and 3 of subsequent task B must be executed sequentially. Therefore, the start time of subtask 3 of task B must start from the end time of subtask 2 of task B. In addition, when subtask 2 of task B starts to work, there are 3 people waiting, and only 2 people are needed for subtask 2 of subsequent task A, so subtask 2 of task A and subtask 2 of task B can start at the same time.

According to the above process, the end time of the last subtask of each parallel task is calculated. The completion time of the four parallel tasks is 80, 85, 125, and 50 minutes, respectively. From this, we know that it takes T=125 minutes in total to complete the work. Let f=1/T=1/125 be the fitness value of the candidate solution x1.

Table 4 Candidate solution 1 decoding process

code string 2 4 4 1 2 2 1 … Starting time 0 0 5 15 30 55 30 … End Time 15 5 10 30 55 60 35 … Number of people waiting 3 1 1 0 3 3 1 …

Since subtask 3 of task A starts after subtask 2 of task B, the constraints are not satisfied. Therefore, the fitness value of this scheduling scheme is f=1/250.

Table 5 shows the completion time and fitness value of the above 9 candidate solutions.

Table 5 Completion time and fitness value of candidate solutions

candidate solution 1 2 3 4 5 6 7 8 9 Completion Time 125 110 140 135 120 110 115 105 105 fitness value f 1/250 1/220 1/280 1/135 1/240 1/110 1/230 1/210 1/105

Step 5: Determine the iteration termination condition.

Assuming that the maximum fitness value of the first 4 iterations is greater than or equal to = 1/110, that is, the shortest completion time has not exceeded 110 minutes for 5 consecutive times, stop the iterative process, and take the code string of candidate solution 6 as the optimal scheduling scheme, otherwise go to step 6.

Step 6, candidate ungrouping.

The 27 candidate solutions obtained in the embodiment are divided into 3 groups according to their suitability values in descending order, and each group has 9 candidate solutions.

Step 7: Calculate the parameters of the distribution model and the range of feasible solutions in groups.

It is assumed that the 9 candidate decompositions in Table 2 are in the same group. Taking the 6th code bit as an example to illustrate the parameter calculation process of the distribution model.

First calculate the number mean of the 6th code bit:

Then calculate the numbered standard deviation of the 6th coded bit:

Finally, calculate the number center of gravity of the 6th code bit:

Then the numbering range of the 6th code bit is: [1.128 2.983]≈[1 3].

If the same method is used to calculate the feasible solution range of the No. 3 code bit: [0.48 5.72]≈[0 6]. Considering that the upper limit of the feature number is 4 and the lower limit is 1, the final feasible solution range of the No. 3 code bit [ 14].

After calculating the feasible solution range of all coded bits of the coded string, go to step 3.

To sum up, the embodiments of the present invention can search for the optimal scheduling scheme in a very short period of time due to the adoption of the grouping optimization and the adaptive adjustment strategy of the search range.

As will be appreciated by those skilled in the art, the embodiments of the present application may be provided as a method, a system, or a computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the present application. It will be understood that each process and/or block in the flowchart illustrations and/or block diagrams, and combinations of processes and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to the processor of a general purpose computer, special purpose computer, embedded processor or other programmable data processing device to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing device produce Means for implementing the functions specified in a flow or flow of a flowchart and/or a block or blocks of a block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory result in an article of manufacture comprising instruction means, the instructions The apparatus implements the functions specified in the flow or flows of the flowcharts and/or the block or blocks of the block diagrams.

These computer program instructions can also be loaded on a computer or other programmable data processing device to cause a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process such that The instructions provide steps for implementing the functions specified in the flow or blocks of the flowcharts and/or the block or blocks of the block diagrams.

The above are only the preferred embodiments of the present invention. It should be pointed out that for those skilled in the art, without departing from the technical principles of the present invention, several improvements and modifications can be made. These improvements and modifications It should also be regarded as the protection scope of the present invention.

Claims (4)

1. a parallel task scheduling method of multiple constraints, is characterized in that, comprises the steps: Step A, set the feature number for each parallel task, form the number pool of the candidate decoding code string; Set the initial feasible solution range; Step B, randomly generate a plurality of candidate decoding strings according to the feasible solution range and the number pool, and calculate the fitness value of the candidate decoding strings; Step C, judge whether the optimization termination condition is satisfied according to the fitness value, then take the candidate decoding string with the highest fitness value as the optimal scheduling scheme, and end the iterative process; otherwise, perform step D; Step D, according to the fitness value of the candidate decoding string, divide the candidate decoding string into several groups, and calculate the distribution model of each group of candidate decoding strings respectively; Step E, calculate the feasible solution range of the candidate decoding code string according to the distribution model grouping, then go to step B; The method for generating the candidate decoding string includes the following steps: Select a code bit of the candidate decoded code string, and randomly select a range of feature numbers from the number pool according to the feasible solution range of the code bit and put it on the code bit. If no feature number that satisfies the feasible solution range is found , then select the feature number closest to the range and put it on the code bit, until all the code bits have placed the feature number, and the resulting encoded string is the generated candidate decoded string; The feasible solution range of the candidate decoding string is determined as follows: Suppose the center of gravity of the kth coded bit of the candidate decoding string is a _k , then the feasible solution range of the coded bit is [ _ak -σ _k a _k +σ _k ], where σ _k is the standard deviation of the kth coded bit , if the range exceeds the permitted range of the feature number, it will be replaced by the permitted range of the feature number. 2. a kind of parallel task scheduling method with multiple constraints according to claim 1, is characterized in that, the formation of described numbering pool comprises the steps: All numbers of the numbering pool consist of feature numbers of parallel tasks, and the number of feature numbers is equal to the number of respective subtasks. 3. a kind of parallel task scheduling method with multiple constraints according to claim 1, is characterized in that, the calculation of candidate decoding string fitness value comprises the following steps: Assuming the final end time of the parallel task is T, its fitness value is 1/T; if the current candidate solution does not meet the preset constraints, a penalty mechanism is enabled: the fitness value is reduced by more than two times. 4. The parallel task scheduling method with multiple constraints according to claim 3, wherein the constraints comprise: 1) Each sub-task in the same task meets the requirements of the sequence of execution and the length of time for completion; 2) The subtasks between different parallel tasks meet the sequence requirements of execution sequence; 3) The total number of people completing parallel tasks and the number of people participating in subtasks meet the quota requirements.

Images