CN102566560B - A kind of production line scheduling method based on structure type heuritic approach - Google Patents

Abstract

The present invention provides a production line scheduling method based on a constructional heuristic algorithm, which includes the following steps: S1. If n workpieces are processed on m machines, set p _{i, j} as the jth workpiece on the i machine Execution time above constitutes a matrix P, where i=1, 2, Λ, m; j=1, 2, Λ, n; S2, select two columns of elements in the matrix P arbitrarily, that is, workpieces a and b are respectively in m Execution time P _a and P _b on two machines, where 1≤a, b≤n, a≠b; S3. Determine the processing sequence of workpieces a and b; S4. Determine whether the elements in the n columns of the matrix P Two comparisons, if yes, end the judgment, adjust the workpiece according to the determined processing sequence, and process it on m machines in turn, otherwise, return to step S2. The invention realizes the scheduling of the flow shop production line with the goal of minimizing the total completion time, and reduces the waiting time of each workpiece before processing by adjusting the processing sequence of the workpieces. Compared with the prior art, the present invention has low calculation complexity, short calculation time and better scheduling performance.

Description

A Production Line Scheduling Method Based on Constructive Heuristic Algorithm

technical field

The invention relates to the field of automatic control and information technology, in particular to a production line scheduling method based on a constructional heuristic algorithm.

Background technique

Production line scheduling is a very important issue in the production process of manufacturing enterprises. A good scheduling strategy will greatly improve production efficiency. The total completion time (makespan) is a very important performance index in the scheduling process. The minimum total completion time can lead to more efficient use of resources, faster delivery of tasks and minimum WIP inventory. The current production line scheduling methods are divided into two types, one is exhaustive method, such as dynamic programming method, branch and bound method, etc., although the processing sequence of workpieces can be optimally scheduled, but the search space of these methods will vary with time. As the number of workpieces increases exponentially, the calculation complexity is high, and the requirements for machine hardware are high, so it is difficult to apply to large-scale production line scheduling; another method is heuristic algorithm, including meta-heuristic algorithm and construction Constructive heuristic algorithms currently proposed such as (1) Palmer algorithm——Palmer D S. Sequencing Jobs through a Multi-Stage Process in the Minimum Total Time-a Quick Method of Obtaining a near Optimum[J]. Operational Research Quarterly, 1965, 16: 101-107; (2) Gupta algorithm - Gupta J.A Functional Heuristic Algorithm for the Flowshop Scheduling Problem [J]. Operational Research Quarterly, 1971, 22: 39-47; (3) CDS algorithm - —Campbell H G, Dudek R A, Smith M L.A Heuristic Algorithm for then-Job, m-Machine Scheduling Problem.[J].Management Science, 1970, 16:630-637; (4) RA Algorithm——Dannenbring D G .An Evaluation of Flow ShopSequencing Heuristics[J].Management Science, 1977, 23(11): 1174-1182; (5) NEH algorithm——Nawaz M, Enscore E, Ham I.A Heuristic Algorithm for the m Machine, n Job Flow Shop [J]. OMEGA: The International Journal of Management Sciences, 1983, 11(1): 91-95, etc. Among the above several constructive heuristic algorithms, the NEH algorithm has the best performance. However, the NEH algorithm needs to calculate and compare the total completion time of the proposed workpiece sequence multiple times during the implementation process, so the computational complexity will be much greater than other stereotyped heuristic algorithms.

Contents of the invention

In view of the problems existing in the prior art, the main purpose of the present invention is to provide a production line scheduling method based on a constructional heuristic algorithm with high scheduling performance and low computational complexity.

In order to achieve the above object, the present invention provides an embodiment of a production line scheduling method based on a constructive heuristic algorithm, the method comprising the following steps:

S1. If n workpieces are processed on m machines, set p _{i, j} as the execution time of the jth workpiece on the i machine, forming a matrix P, where i=1, 2, Λ, m; j= 1, 2, Λ, n;

S2. Arbitrarily select two columns of elements in the matrix P, that is, the execution times P _a and P _b of the workpieces a and b on m machines respectively, where 1≤a, b≤n, a≠b;

S3. Determine the processing sequence of workpieces a and b;

S4, judge whether the n column elements in the matrix P have been compared in pairs, if so, then end the judgment, otherwise, return to step S2,

Wherein step S3 comprises the following steps:

S31. Substituting the values of elements P _a and P _b in the two columns of matrix P into Calculate S _a and S _b ;

S32. Judging whether S _a * S _b <= 0 is true, if true, go to step S321, if not, go to step S33;

S321. Determine whether S _a > 0 is true, if true, place the processing sequence of component a before component b, and if not, place the processing sequence of component b before component a;

S33. Judging whether S _a , S _b > 0 is true, if true, go to step S34, if not, go to step S35;

S34. Substituting the values of the two columns of elements P _a and P _b in the arbitrarily selected matrix P into Calculate sum_c _a and sum_c _b ;

S341. Determine whether sum_c _a < sum_c _b is true, if true, place the processing sequence of component a before component b; if not, proceed to step S342;

S342, judging whether sum_c _a > sum_c _b is true, if true, place the processing sequence of component b before component a, if not true, remove the last element in the P _a and P _b columns and return to step S31;

S35. Substituting the values of the two columns of elements P _a and P _b in the arbitrarily selected matrix P into Calculate sum_f _a and sum_f _b ;

S351. Determine whether sum_f _a > sum_f _b is true, if true, place the processing sequence of component a before component b, if not, go to step S352;

S352. Determine whether sum_f _a < sum_f _b is true. If true, place the processing sequence of component b before component a. If not, remove the first element in columns P _a and P _b and return to step S31.

Further, when the n columns of elements in the judgment matrix P have been compared pairwise, the workpieces are adjusted according to the determined processing sequence, and processed on m machines in sequence.

The invention realizes the scheduling of the flow shop production line with the goal of minimizing the total completion time, and reduces the waiting time of each workpiece before processing by adjusting the processing sequence of the workpieces. Compared with the prior art, the present invention has low calculation complexity, short calculation time and better scheduling performance.

Description of drawings

Figure 1 is a schematic diagram of the production line scheduling in the flow shop.

Fig. 2 is a flow chart of the production line scheduling method based on the stereotype heuristic algorithm of the present invention.

Fig. 3 is a flowchart of step S3 in the production line scheduling method based on the stereotype heuristic algorithm of the present invention.

Detailed ways

The specific implementation manner of the present invention will be described in detail below in conjunction with the accompanying drawings.

As shown in Figure 1, it is a schematic diagram of the production line scheduling of the flow shop of the present invention, which is expressed as n workpieces are processed on m machines, that is, each workpiece needs to go through m processes, and each process requires different machines, but n workpieces The order of passing through m machines is the same, that is, the processing order of n workpieces on each machine is the same. That is, workpiece 1, workpiece 2...workpiece n are respectively processed by machine 1, machine 2...machine m in sequence, but this processing sequence may not be optimal. In order to make the total The processing time is the shortest, and the processing sequence of the workpieces must be adjusted.

Define O _{i, j} as the j-th workpiece operating on the i machine, p _{i, j} is the execution time of O _{i, j,} c _{i, j} is the completion time of O _{i, j,} and c _{i, j} is O _{i, j} plus waiting time. where i=1, 2, Λ, m; j=1, 2, Λ, n. In order to determine the optimal processing sequence of the processing tasks of n workpieces on each machine, the time to complete the processing tasks of all workpieces is the shortest. When processing workpieces, the processing sequence of each processing task on the machine is the same, which is 1, 2, Λ, m; each machine can only perform one processing task at the same time; one processing task cannot be performed on different machines at the same time ; Each processing task is sent to the next process immediately after processing; the task starts to process on the machine, and must continue until the process is completed, and it is not allowed to stop and insert other tasks in the middle; all tasks are ready at time 0, and the machine adjusts the time Included in processing time; allowing tasks to wait between operations; allowing machines to sit idle while tasks do not arrive. The maximum completion time makespan(C _max ) is also the completion time c _{m, n} of the last workpiece processing. Find the processing sequence of a workpiece, workpiece a, workpiece b...job n, so that the total completion time (makespan ) minimum.

Let the total completion time (makespan) when the number of workpieces is i be C _i , where 1≤i≤n, when i=n, define C _i =C _n =C; suppose the jth workpiece is on the i machine The waiting time before processing is t _{i, j} , where t _{i, 1} = 0, 1≤i≤m, 1≤j≤n; let the waiting time of the nth workpiece before being processed on the i machine be D _i , where D ₁ =0, that is, the waiting time of all workpieces on the first machine is 0, 1≤i≤m; let the processing time matrix of n workpieces on m machines be P, where: $P=\left(\begin{array}{cccc}{p}_{\mathrm{1,1}}& p_{\mathrm{1,2}}& \mathrm{\&Lambda;}& p_{1,\mathrm{no}}\\ p_{\mathrm{2,1}}& p_{\mathrm{2,2}}& \mathrm{\&Lambda;}& p_{2,\mathrm{no}}\\ m& m& o& m\\ p_{m,1}& p_{m,2}& \mathrm{\&Lambda;}& p_{m,\mathrm{no}}\end{array}\right),$ In the matrix P, p _{i, j} represent the processing time of the jth workpiece on the i machine, 1≤i≤m, 1≤j≤n.

When the number of workpieces is 1, that is, when n=1, the waiting time before the workpiece is processed on each machine is 0, so the total completion time (makespan) is the sum of the processing time of the workpiece on all machines: $C_1=p_{\mathrm{1,1}}+p_{\mathrm{2,1}}+\mathrm{\&Lambda;}+p_{m,1}=\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{p}_{i,1};$

When the number of workpieces is 2, that is, when n=2, the total completion time (makespan) is the sum of the processing time of the first workpiece on all machines, the processing time of the second workpiece on the last machine and the second The sum of the waiting time of the workpiece on the last machine before processing: C ₂ =C ₁ +p _m,2 +D ₂ , and D ₂ =t _2,n can be calculated as follows: t _2,2 = max(p _2,1 -p _1,2,0 ), t _2,3 =max(t _2,2 +p _2,2 -p' _1,3,0 ), Λ,t _2,n =max( t _2,n-1 +p _2,n-1 -p′ _1,n ,0), where p′ _i,j =p _i,j +max(p _i-1,j -p _j,i-1 , 0), 2≤i≤m, 1≤j≤n;

By analogy, when the number of workpieces is n, C _n =C _n-1 +p _m,n +D _n , and D _n =t _m,n can be calculated as follows: t _m,2 =max(p _{m, 1} -p' _{m-1, 2} , 0), t _{m, 3} = max(t _{m, 2} +p _{m, 2} -p' _{m-1, 3} , 0), Λ, t _{m, n} = max(t _{m, n-1} + p _{m, n-1} -p' _{m-1, n} , 0). Right now:

$\mathrm{<span\; class="notranslate">\; make\; span</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; =</span>$

${\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}$

$<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}$

$<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}$

$\mathrm{<span\; class="notranslate">\; m</span>}$

$<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; 1,1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; 2,1</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&Lambda;</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&Lambda;</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&Lambda;</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}$

$<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}$

To minimize the total completion time (makespan), it is necessary to find a workpiece processing sequence so that the completion time of the nth workpiece on the mth machine is as close to or equal to That is to reduce the sum of the processing time of the first workpiece on all machines, the sum of the processing time of other workpieces except the first workpiece on the last machine, and the processing time of other workpieces except the first workpiece before processing sum of waiting times.

As shown in Figure 2, it is a flow chart of the production line scheduling method based on the constructional heuristic algorithm of the present invention, and the method includes the following steps:

S1. If n workpieces are processed on m machines, let p _{i, j} be the execution time of the jth workpiece on the i machine, forming a matrix P, $P=\left(\begin{array}{cccc}{p}_{\mathrm{1,1}}& p_{\mathrm{1,2}}& \mathrm{\&Lambda;}& p_{1,\mathrm{no}}\\ p_{\mathrm{2,1}}& p_{\mathrm{2,2}}& \mathrm{\&Lambda;}& p_{2,\mathrm{no}}\\ m& m& o& m\\ p_{m,1}& p_{m,2}& \mathrm{\&Lambda;}& p_{m,\mathrm{no}}\end{array}\right),$ Wherein i=1,2,Λ,m; j=1,2,Λ,n;

S2. Arbitrarily select two columns of elements in the matrix P, that is, the execution times P _a and P _b of the workpieces a and b on m machines respectively, where 1≤a, b≤n, a≠b;

S3. Determine the processing sequence of workpieces a and b;

S4. Judging whether the elements in the n columns in the matrix P have been compared in pairs. If so, end the judgment, adjust the workpiece according to the determined processing sequence, and process it on m machines in turn, otherwise, return to step S2.

As shown in FIG. 3 , it is a flowchart of step S3 in the production line scheduling method based on the stereotype heuristic algorithm of the present invention. Step S3, that is to determine the processing sequence of workpieces a and b, specifically includes the following steps:

S31. Substituting the values of elements P _a and P _b in the two columns of matrix P into (S _j is the weighted value of column j in the matrix P), calculate S _a and S _b ;

S32. Judging whether S _a * S _b <= 0 is true, if true, go to step S321, if not, go to step S33;

S321. Judging whether S _a > 0 is true, if true, proceed to step S322, that is, place the processing sequence of component a before component b, and if not, proceed to step S323, that is, place the processing sequence of component b before component a;

S33. Judging whether S _a , S _b > 0 is true, if true, go to step S34, if not, go to step S35;

S34. Substituting the elements P _a and P _b in the two columns of the matrix P selected arbitrarily into (sum_c _j is the sum of constantly removing the last element of column j in the matrix P), calculate sum_c _a and sum_c _b ;

S341. Judging whether sum_c _a < sum_c _b is true, if true, proceed to step S343, that is, place the processing sequence of component a before component b; if not, proceed to step S342;

S342. Determine whether sum_c _a > sum_c _b is true, if true, enter step S345, that is, place the processing sequence of component b before component a, if not, it can be seen that sum_c _a = sum_c _b , then enter step S344, that is, remove P _a and the last element of the P _b column and return to step S31;

S35. Substituting the elements P _a and P _b in the two columns of the matrix P selected arbitrarily into (sum_f _j is to constantly remove the sum of the first element in the jth column in the matrix P), calculate sum_f _a and sum_f _b ;

S351. Determine whether sum_f _a > sum_f _b is true, if true, proceed to step S353, that is, place the processing sequence of component a before component b, and if not, proceed to step S352;

S352. Determine whether sum_f _a < sum_f _b is true. If true, proceed to step S355, that is, place the processing sequence of component b before component a. If not, it can be known that sum_f _a = sum_f _b , then proceed to step S354, that is, remove P _a and the first element of column P _b and return to step S31.

The actual scheduling performance of the production line scheduling method based on the stereotype heuristic algorithm of the present invention is illustrated by the experimental results. Among them, Y is the optimal rate, that is, in a specific sample size, the proportion of the optimal solution obtained by using a certain scheduling method accounts for the proportion of all samples. The higher the value, the higher the proportion of the optimal solution obtained by using the scheduling method. High, better performance. In addition, the optimal deviation rate E=(MK-MKp)·100/MKp, where MK is the actual total completion time of the workpieces sorted by a certain scheduling method, and MKp is the total completion time of the group of workpieces in the optimal processing order , the smaller the optimal deviation rate E is, the better the arrangement of the workpiece processing sequence is by using a certain scheduling method, and E=0 indicates that the processing sequence of a certain workpiece is optimal.

Each element Pi in the processing time matrix P of the workpiece used in the experiment on each machine, j is a random integer from 0 to 9 (1≤i≤m, 1≤j≤n), the following table gives a number of The test data with a sample size of 20 as a unit can be seen from the following table, using the production line scheduling method based on the constructional heuristic algorithm of the present invention, the optimal deviation rate E>10% is very small, and the average optimal deviation rate is basically in the Below 5%, it shows that the scheduling performance of this method is better. In addition, the algorithm complexity of the production line scheduling method based on the constructional heuristic algorithm of the present invention is nlog(n)+nm, the calculation complexity is low, and the calculation time is short.

Embodiment one

Assuming that the processing time matrix P of 5 workpieces on 4 machines is as follows, P _i represents the i-th column of P.

$\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; =</span>\left(\begin{array}{ccccc}\mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 7</span>}& \mathrm{<span\; class="notranslate">\; 7</span>}\\ \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 9</span>}& \mathrm{<span\; class="notranslate">\; 9</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}\\ \mathrm{<span\; class="notranslate">\; 9</span>}& \mathrm{<span\; class="notranslate">\; 7</span>}& \mathrm{<span\; class="notranslate">\; 3</span>}& \mathrm{<span\; class="notranslate">\; 7</span>}& \mathrm{<span\; class="notranslate">\; 7</span>}\\ \mathrm{<span\; class="notranslate">\; 10</span>}& \mathrm{<span\; class="notranslate">\; 6</span>}& \mathrm{<span\; class="notranslate">\; 8</span>}& \mathrm{<span\; class="notranslate">\; 7</span>}& \mathrm{<span\; class="notranslate">\; 2</span>}\end{array}\right)$

Arbitrarily select two columns of elements P ₁ and P ₂ in the matrix P;

Substitute the values of P ₁ and P ₂ into Calculated to get S ₁ =33, S ₂ =13;

Since S ₁ and S ₂ >0, substitute the values of P ₁ and P ₂ into Calculate sum_C ₁ =13, sum_C ₂ =17;

Because sum_C ₁ < sum_C ₂ , the processing sequence of P ₁ is placed before P ₂ ;

Arbitrarily select two columns of elements P ₁ and P ₃ in the matrix P;

Substitute the values of P ₁ and P ₃ into Calculated to get S ₁ =33, S ₃ =9;

Since S ₁ and S ₃ >0, substitute the values of P ₁ and P ₃ into Calculate sum_C ₁ =13, sum_C ₃ =15;

Because sum_C ₁ < sum_C ₃ , the processing sequence of P ₁ is placed before P3;

Arbitrarily select two columns of elements P ₁ and P ₄ in the matrix P;

Substitute the values of P ₁ and P ₄ into Calculated to get S ₁ =33, S ₄ =4;

Since S ₁ and S ₄ >0, substitute the values of P ₁ and P ₄ into Calculate sum_C ₁ =13, sum_C ₄ =16;

Because sum_C ₁ < sum_C ₄ , the processing sequence of P ₁ is placed before P ₄ ;

Arbitrarily select two columns of elements P ₁ and P ₅ in the matrix P;

Substitute the values of P ₁ and P ₅ into Calculated to get S ₁ =33, S ₅ =-10;

Since S ₁ ·S ₅ <=0, and S ₁ >0, the processing sequence of P ₁ is placed before P ₅ ;

Arbitrarily select two columns of elements P ₂ and P ₃ in the matrix P;

Substitute the values of P ₂ and P ₃ into Calculated to get S ₂ =13, S ₃ =9;

Since S ₂ and S ₃ >0, substitute the values of P ₂ and P ₃ into Calculate sum_C ₂ =17, sum_C ₃ =15;

Because sum_C ₂ > sum_C ₃ , the processing sequence of P ₃ is placed before P ₂ ;

Arbitrarily select two columns of elements P ₂ and P ₄ in the matrix P;

Substitute the values of P ₂ and P ₄ into It is calculated that S ₂ =13, S ₄ =4;

Because S ₂ , S ₄ >0, substitute the values of P ₂ and P ₄ into Calculate sum_C ₂ =17, sum_C ₄ =16;

Because sum_C ₂ > sum_C ₄ , the processing sequence of P ₄ is placed before P ₂ ;

Arbitrarily select two columns of elements P ₂ and P ₅ in the matrix P;

Substitute the values of P ₂ and P ₅ into Calculated to get S ₂ =13, S ₅ =-10;

Since S ₂ ·S ₅ <=0, and S ₂ >0, the processing sequence of P ₂ is placed before P ₅ ;

Arbitrarily select two columns of elements P ₃ and P ₄ in the matrix P;

Substitute the values of P ₃ and P ₄ into Calculated to get S ₃ =9, S ₄ =4;

Since S ₃ and S ₄ >0, substitute the values of P ₃ and P ₄ into Calculate sum_C ₃ =15, sum_C ₄ =16;

Because sum_C ₃ < sum_C ₄ , the processing sequence of P ₃ is placed before P ₄ ;

Arbitrarily select two columns of elements P ₃ and P ₅ in the matrix P;

Substitute the values of P ₃ and P ₅ into Calculated to get S ₃ =9, S ₅ =-10;

Since S ₃ ·S ₅ <=0, and S ₃ >0, the processing sequence of P ₃ is placed before P ₅ ;

Arbitrarily select two columns of elements P ₄ and P ₅ in the matrix P;

Substitute the values of P ₄ and P ₅ into Calculated to get S ₄ =4, S ₅ =-10;

Since S ₄ ·S ₅ <=0, and S ₄ >0, the processing sequence of P ₄ is placed before P ₅ ;

The elements in the 5 columns in the matrix P have been compared in pairs, and the final processing sequence of each workpiece is P ₁ P ₃ P ₄ P ₂ P ₅ .

Adjust the processing sequence of workpieces to P ₁ P ₃ P ₄ P ₂ P ₅ , and process them on m machines in turn.

The production line scheduling method based on the constructional heuristic algorithm is introduced above. The present invention is not limited to the above embodiments, and any improvement or change that does not deviate from the technical solution of the present invention, that is, only improvements or changes known to those skilled in the art, falls within the protection scope of the present invention.

Claims (2)

1., based on a production line scheduling method for structure type heuritic approach, comprise following steps:

If a S1 n workpiece is processed on m platform machine, if p _i,jfor the execution time of a jth workpiece on i-th machine, form matrix P, wherein i=1,2 ..., m; J=1,2 ..., n;

Two column elements in S2, arbitrarily selection matrix P, i.e. workpiece a, the b execution time P respectively on m platform machine _aand P _b, wherein 1≤a≤n, 1≤b≤n, a ≠ b;

S3, determine workpiece a, the processing sequence of b;

Whether the n column element in S4, judgment matrix P all compares between two, if so, then terminates to judge, otherwise, return step S2,

It is characterized in that, described step S3 comprises following steps:

S31, by two column element P in matrix P _a, P _bvalue substitute into respectively calculate S _aand S _b;

S32, judge S _a* S _bwhether <=0 sets up, if set up, then enters step S321, if be false, then enters step S33;

S321, judge S _awhether >0 sets up, if set up, then before the processing sequence of element a being placed in element b, if be false, then before the processing sequence of element b being placed in element a;

S33, judge S _a>0 and S _bwhether >0 sets up, if set up, then enters step S34, if be false, then enters step S35;

S34, by two column element P in optional matrix P _a, P _bvalue substitute into respectively calculate sum_c _aand sum_c _b;

S341, judge sum_c _a<sum_c _bwhether set up, if set up, then before the processing sequence of element a being placed in element b; If be false, then enter step S342;

S342, judge sum_c _a>sum_c _bwhether set up, if set up, then, before the processing sequence of element b being placed in element a, if be false, then remove P _aand P _bthe last element arranged also returns step S31;

S35, by two column element P in optional matrix P _a, P _bvalue substitute into respectively calculate sum_f _aand sum_f _b;

S351, judge sum_f _a>sum_f _bwhether set up, if set up, then, before the processing sequence of element a being placed in element b, if be false, then enter step S352;

S352, judge sum_f _a<sum_f _bwhether set up, if set up, then, before the processing sequence of element b being placed in element a, if be false, then remove P _aand P _bthe first element arranged also returns step S31.

2. as claimed in claim 1 based on the production line scheduling method of structure type heuritic approach, it is characterized in that: when the n column element in judgment matrix P all compares between two, then by the processing sequence determined, workpiece is adjusted, and process on m platform machine successively.