Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Comprehensive scheduling method based on Dijkstra algorithm

A scheduling method and algorithm technology, applied in computing, manufacturing computing systems, instruments, etc., can solve the problems of horizontal and vertical optimization, ignoring the impact of scheduling effects, and low utilization of processing equipment

Active Publication Date: 2020-07-03
JILIN NORMAL UNIV
View PDF7 Cites 7 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0003] Although the existing comprehensive scheduling algorithm has achieved good research results, there are still problems in the horizontal and vertical optimization.
For example, the dynamic Job-Shop method based on ACMP and BFSM proposes a critical path algorithm based on the longitudinal processing process, but ignores the parallel processing capability of the equipment; the method of closely linking the linkage of process groups proposes to determine the scheduling by the total number of processes The algorithm of path and sequence, but ignores the impact of the scheduling of leaf node processes on the overall scheduling effect; the timing method considering the compactness of serial processes proposes an algorithm that takes the number of serial processes as the sorting strategy, but ignores the processing of the process itself The impact of time usage on the overall scheduling effect
[0004] Aiming at the low utilization rate of processing equipment and the existence of many idle time periods in many comprehensive scheduling methods, an improved Dijkstra algorithm is proposed that uses the processing time of the process itself as the path assignment, and constructs a priority scheduling strategy based on layers and leaf nodes comprehensive scheduling method

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Comprehensive scheduling method based on Dijkstra algorithm
  • Comprehensive scheduling method based on Dijkstra algorithm
  • Comprehensive scheduling method based on Dijkstra algorithm

Examples

Experimental program
Comparison scheme
Effect test

Embodiment

[0095] For further setting forth method of the present invention, design complex product process tree such as figure 2 As shown, there are 11 layers and 27 processing steps. It should be noted that this calculation example does not specifically refer to a certain type of product, and the method described in the present invention is also applicable to other complex products with small batches and multiple varieties.

[0096] will be like figure 2 The complex product process tree shown is converted into a directed graph with the processing time of the process itself as the path value, as shown in image 3 shown.

[0097] 1. Path and path value of each process

[0098] Calculated according to the improved Dijkstra algorithm as image 3 Table 1 shows the paths and path values ​​from the root node process to each node process in the directed graph of the complex product process tree shown.

[0099] Table 1 Statistical table of paths and path values ​​from the root node proce...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a comprehensive scheduling method based on a Dijkstra algorithm, and the method comprises the steps: extracting the processing time of each process according to the natural attribute of a complex product process, and carrying out the path assignment of all processes; calculating a layer priority, an equipment priority and a process constraint degree of each process; according to a Dijkstra algorithm, respectively calculating path values from the root node process to all other processes; and according to the path value judgment strategy, the layer priority judgment strategy and the leaf node process judgment strategy, reversely scheduling each process according to the shortest path principle. The method provided by the invention provides a new method for solving comprehensive scheduling of general complex products, expands thinking for further deep research on comprehensive scheduling, and has certain theoretical and practical significance.

Description

technical field [0001] The invention relates to the technical field of computer integrated manufacturing, in particular to an integrated scheduling method based on Dijkstra algorithm. Specifically, the self-processing time of complex product processing procedures is used as the path value of the improved Dijkstra algorithm, and a comprehensive scheduling method is constructed with layer and leaf node priority scheduling strategies. Background technique [0002] The scheduling problem of product manufacturing is an important factor affecting the production efficiency of the manufacturing industry. Under the premise of fixed conditions such as enterprise equipment and resources, the efficiency of scheduling directly determines the production efficiency of the enterprise. In order to better solve the scheduling problem of small-batch and multi-variety production, some experts and scholars proposed a comprehensive scheduling that handles product processing and assembly together,...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06Q10/04G06Q10/06G06Q50/04
CPCG06Q10/047G06Q10/06316G06Q50/04Y02P90/30
Inventor 周伟孙明李丽颖王晓宇英昌盛周芃玮
Owner JILIN NORMAL UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products