Production line scheduling method based on constructive heuristic algorithm

Abstract

The invention provides a production line scheduling method based on a constructive heuristic algorithm. The method comprises the following steps: S1, setting p(i, j) as the execution time of a jth workpiece on an ith machine if n workpieces are processed on m machines, and constructing a matrix P, wherein i is a natural number from 1 to m, and j is a natural number from 1 to n; S2, randomly selecting two columns of elements in the matrix P, namely the execution time Pa and Pb of workpieces (a, b) on the m machines, wherein a is less than or equal to 1, b is less than or equal to n, and a is not equal to b; S3, determining the processing sequence of the workpieces (a, b); and S4, determining whether n columns of elements in the matrix P are compared pairwise, stopping determination if the n columns of elements are compared, adjusting the workpieces according to the determined processing sequence, and sequentially processing the workpieces on the m machines, otherwise, returning to the step S2. The production line scheduling method provided by the invention can be used for scheduling the production line of a flow shop to achieve the shortest total completion time, and reducing the waiting time of each workpiece before processing by adjusting the workpiece processing sequence. Compared with the prior art, the method provided by the invention has the advantages of low computation complexity, short computation time and better scheduling performance.

Description

technical field [0001] 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 [0002] 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 increase...

AI Technical Summary

Problems solved by technology

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 Shop Sequencing 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, in the implementation process of the NEH algorithm, the total completion time of the proposed workpiece sequence needs to be calculated and compared multiple times, so the computational complexity will be much greater than that of other stereotyped heuristic algorithms

Images