论文部分内容阅读
企业的置换装配线调度问题(Permutation Assembly-line Scheduling Problem,PASP)是一类典型的NPhard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明:本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。
Enterprise Permutation Assembly-Line Scheduling Problem (PASP) is a typical NPhard-type production scheduling problem, which is very concerned by modern integrated manufacturing system CIMS. The problem can be described in detail as n pieces of work to be machined on m machines, and each piece of work needs to go through m passes, each requiring a different machine, which passes through the same order of m machines, The machining sequence on the machine is also the same. The main objective of the problem is to find the optimal machining sequence for n workpieces on each machine so that the maximum finishing time is minimized. Due to the NP-hard nature of PASP problem, this paper uses genetic algorithm to solve it. Although genetic algorithms are commonly used to solve scheduling problems, their selection and crossover mechanisms easily lead to local optimization and slow convergence. Therefore, this paper proposes an improved genetic algorithm based on block mining and reorganization to solve the problem of replacement assembly line scheduling. Firstly, different excellent genes are extracted through association rules, then the genes with better results are combined into dominant blocks to produce artificial solutions with superiority, and local search methods with high convergence are introduced to improve the chance of finding the optimal solution With convergence efficiency. In this paper, we use the Taillard standard test in OR-Library to verify the quality and efficiency of the improved genetic algorithm. The results show that the proposed algorithm not only converges faster than the other five well-known algorithms for solving scheduling problems, Solving quality is better than them.