基于遗传算法与仿真的生产作业排序系统研究与开发

Scheduling and sequencing problems have attracted the attentions of researchers from various fields for many years, such as production management, computer science, and combinatorial optimization. This problem is very important in both theoretical and practical aspects because it is essential for improving the total management efficiency so as to achieve much larger economic gains. However, scheduling problems are generally with high computational complexity (NP-Hard), and hard to be solved with traditional approaches. In this project, a hybrid algorithm framework based on the integration of genetic algorithm and simulation is proposed, in which genetic algorithms and heuristic methods are combined through a simulation process. With this framework, domain knowledge relevant to specific problems can be employed and represented as heuristic rules which can be introduced into genetic algorithms with the aid of an embedded simulator to guide the searching process of the algorithm. This integration scheme is not only with help for improving the search efficiency, but also with high flexibility for designing the specific algorithms. In addition, the performance of heuristic methods can be greatly improved with the help of the optimization power of genetic algorithms under this framework. Hence by this framework we can take the advantage of complement of the two approaches. Based on the above algorithm framework, various simulation models and heuristic rules have been established and integrated with genetic algorithms to construct the appropriate scheduling algorithms for different production environments (e.g., job shop problems which minimize makespan, scheduling for minimizing tardiness, problems involving time-dependent setup times, and scheduling problems with multiple objectives). All the algorithms have been proved to be satisfactory in both effectiveness and efficiency performance by comprehensive numerical experiments, and some results have achieved the best values which can be found till now. Therefor, the algorithm framework is quite robust for different problems. A prototype of algorithm system based on genetic search and simulation has been developed, which can provide basic supports for production scheduling. Finally, some primary positive studies have been conducted in a manufacturing enterprise.

针对当前作业排序领域存在的总是建立基于遗传算法怀系统仿真的集成算法系统，对各种实际生产作业排序问题建立相应的启发式方法，借助仿真将遗传算法与启发式方法相结合，利用仿真手段增强对实际问题的建模能力和对排序策略的分析能力，利用遗传算法改进启发式方法的性能，同时利用启发式规则引导遗传算法的搜索过程，以提高算法效率。