作　　者： ; ; ; ;

机构地区： 昆明理工大学

出　　处： 《中国管理科学》 2016年第12期63-71,共9页

摘　　要： 企业的置换装配线调度问题(Permutation Assembly-line Scheduling Problem,PASP)是一类典型的NPhard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明:本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。 The Permutation Assembly-line Scheduling Problem(PASP)is a kind of typical production scheduling problem,which has the property of NP-Hard and is the key of Computer Integrated Manufacturing System(CIMS).This problem can be described as follows:N jobs are proceeded in M machines;each job requires M working procedures,of which each procedure requires different machine;they go through the machines in the same order while the processing sequence are also the same in each machines.The main goal for the problem is to find out the optimal processing sequence of N jobs in each machine to minimize the makespan.Genetic algorithm is one kind of heuristic algorithms used to solve permutation Assembly-line scheduling problem(PASP).However,the offspring is difficult to have various genes in good solutions because of the evolution of its selection and crossover mechanism and then leads to local optimum.This paper aims to propose an improved genetic algorithm based on block mining with recombination for solving PASP,in which association rule is used to extract various good genes and increase the gene diversity.These genes are also used to generate various block for artificial chromosome combination.The generated blocks can not only improves the opportunities of finding optimal solutions but also enhance the efficiency of convergence.The proposed algorithm is validated and compared with other five algorithms by numerical experiments,namely Taillard in OR-Library.To compare with other algorithms,the solutions of proposed algorithm are closest to the optimal solution.The results show that proposed algorithm can have not only high the convergence speed but also better solution quality by increasing the solutions diversity.

关 键 词： 组合优化 装配线调度 关联规则 改进遗传算法 人工解

领　　域： [自动化与计算机技术] [自动化与计算机技术]