Production planning and scheduling method based on graph coloring

Abstract

The invention discloses a production planning and scheduling method based on graph coloring, and the method comprises the steps: S1, building a graph coloring model according to a production plan and a scheduling task, and decomposing the graph coloring model into a series of planar graphs; s2, converting each plane graph into a plane line graph; s3, carrying out planar graph coloring on each planar line graph; s4, sequentially performing color fixation on nodes of each planar graph according to the generation sequence of the planar graphs; and S5, determining a production plan and a scheduling result according to the color of each node in the graph coloring model. According to the method provided by the invention, a difficult large-scale graph coloring solving problem is decomposed into a small planar graph four-color coloring problem which is proved by the existing computer theory, so that the solving difficulty is greatly reduced; problems of distribution of production tasks at stations and the like, distribution of the production tasks at work groups, distribution of airport flights at boarding gates, arrangement of examination time tables and the like in production planning and scheduling can be efficiently and accurately solved.

Description

technical field [0001] The invention belongs to the field of production planning and scheduling, and more particularly, relates to a production planning and scheduling method based on graph coloring. Background technique [0002] The production of modern enterprises is inseparable from the production planning and scheduling system. An excellent production planning and scheduling system can greatly improve the production efficiency of an enterprise, reduce waste and improve efficiency. The core of the production planning and scheduling system is the production planning and scheduling solution method. Different enterprises have different production planning and scheduling tasks, but the distribution of production tasks in workstations, the allocation of production tasks in working groups, and the allocation of airport boarding gates are essentially the same for different companies. If the application of the problem is extended, there are many other problems in the society th...

AI Technical Summary

Problems solved by technology

[0006] Aiming at the above defects or improvement needs of the prior art, the present invention provides a production planning and scheduling method based on graph coloring, thereby solving the technical problem that the accuracy and efficiency of the existing method are difficult to balance simultaneously

Images