两阶段装配流水车间生产运输集成调度研究

发布时间：2018-04-04 06:47

本文选题：两阶段装配流水车间　切入点：集成调度　出处：《武汉大学》2017年硕士论文

【摘要】：两阶段装配流水车间调度(Two-Stage Assembly Flowshop Scheduling Problem,TSAFSP)属于经典的组合优化问题,广泛存在于制造企业中。随着竞争的加剧,客户需求的多样化要求企业能够在适当的时间完成产品运输,这就需要企业在确定调度方案时能同时考虑生产阶段和运输阶段,本文对两阶段装配流水车间生产运输集成调度问题(Two-Stage Assembly Flowshop Scheduling Problem with Batch Delivery,TSAFSP-BD)进行了研究。该问题基于实际生产领域需求,不仅研究制造企业生产过程中的工件调度,还研究生产结束后产品的批量运输,可有效提升企业整体效率,降低不必要的库存持有成本、提前惩罚成本、延迟惩罚成本等。TSAFSP-BD问题具有强NP难特性,需要采用近似算法进行求解,本文采用混合优化策略,提出了一种基于遗传算法(GeneticAlgorithm,GA)与反向变邻域搜索(Opposition-Based Variable Neighborhood Search,OVNS)的混合智能优化算法GA-OVNS。GA作为一种广泛应用的全局优化策略,通过采用交叉、变异操作进行优化迭代,从而获取最优解。但由于其缺乏连锁学习的能力,局部搜索能力较差,容易导致算法过早收敛。VNS(Variable Neighborhood Search,VNS)作为一种局部搜索算法,通过搜索邻域结构集获取最优解,其最优解的质量依赖于邻域结构。OVNS中结合了反向学习(Opposition-Based Learning,OBL)思想,在构造邻域结构的同时考虑反向邻域结构,扩大邻域结构集,提升局部搜索能力。因此,本文采用基于GA和OVNS的混合智能优化方法GA-OVNS求解TSAFSP-BD问题,能有效提高算法的全局搜索功能和局部搜索功能,主要研究内容如下:对于单客户下TSAFSP-BD问题,GA-OVNS采用基于工序的扩展编码,即第一行为工件的加工次序,第二行用于划分产品运输批次,为了提高初始解的质量,在随机产生的初始种群中加入部分基于SPT(Shortest Processing Time)规则生成的个体。种群采取两点交叉和改进变异操作进行迭代,每代种群的最优解作为OVNS的初始解。OVNS在采用插入、交换、逆序等邻域结构的同时,通过构造基于OBL的反向邻域结构增加搜索范围,从而快速有效地快速有效地求解该问题。对于多客户下TSAFSP-BD问题,在进行迭代的过程中需要明确划分工件的客户群体,因此需要针对提出的GA-OVNS的原有编码方式行改进,同时识别产品的运输批次以及客户群体,并在迭代的过程中合理调整交叉、变异、邻域搜索等操作,避免出现解码混乱。考虑到实际生产中需要同时优化多个目标的情况,本文以最小化库存持有成本、提前惩罚成本、期惩罚成本以及运输费用为目标,将GA-OVNS和启发式启发式算法 EDD(Earliest Due Data Rule)、SLACK(Slack Time Rule)以及智能优化算法GA、GA-VNS进行比较。混合智能优化方法各参数设置采用正交试验设计进行确定。通过多组算例测试,实验结果表明GA-OVNS的优化性能优于其他算法。
[Abstract]:Two-Stage Assembly Flowshop Scheduling problem of Two-Stage Assembly Scheduling problem (TSAFSP), which is widely used in manufacturing enterprises, belongs to the classical combinatorial optimization problem.With the intensification of competition, the diversification of customer demand requires enterprises to complete product transportation in an appropriate time, which requires enterprises to consider both production and transportation stages when determining scheduling schemes.In this paper, the Two-Stage Assembly Flowshop Scheduling Problem with Batch delivery problem TSAFSP-BDD of two-stage assembly income workshop is studied.This problem is based on the actual production requirements. It not only studies the scheduling of jobs in the production process of manufacturing enterprises, but also studies the batch transportation of products after the end of production, which can effectively improve the overall efficiency of enterprises and reduce the unnecessary inventory holding costs.The TSAFSP-BD problem has strong NP-hard properties and needs to be solved by approximate algorithm. In this paper, a hybrid optimization strategy is used to solve TSAFSP-BD problem.A hybrid intelligent optimization algorithm (GA-OVNS.GA) based on genetic algorithm (GA) and reverse variable neighborhood search (GA-OVNS.GA) is proposed as a widely used global optimization strategy. The optimal solution is obtained by using crossover and mutation operations.However, due to its lack of linkage learning ability and poor local search ability, it is easy to lead to premature convergence of the algorithm. As a local search algorithm, the optimal solution can be obtained by searching the neighborhood structure set.The quality of the optimal solution depends on the neighborhood structure. OVNS combines the idea of reverse learning Opposition-Based learning OBL.Constructing the neighborhood structure, the reverse neighborhood structure is considered at the same time, the set of neighborhood structures is enlarged, and the local search ability is improved.Therefore, in this paper, the hybrid intelligent optimization method based on GA and OVNS, GA-OVNS, is used to solve the TSAFSP-BD problem, which can effectively improve the global search function and the local search function of the algorithm.The main research contents are as follows: for single customer TSAFSP-BD problem, GA-OVNS adopts the extended coding based on working procedure, that is, the processing order of the first behavior work piece, the second line is used to divide the product transportation batch, in order to improve the quality of the initial solution,An individual generated by the SPT(Shortest Processing time rule is added to the randomly generated initial population.The population adopts two points crossing and improved mutation operation to iterate. The optimal solution of each generation population as the initial solution of OVNS. OVNS uses neighborhood structure such as insert, exchange, reverse order, and increases the search range by constructing the reverse neighborhood structure based on OBL.Thus the problem can be solved quickly and efficiently.For the multi-customer TSAFSP-BD problem, it is necessary to clearly divide the client group of the workpiece in the process of iteration, so it is necessary to improve the original coding method of the proposed GA-OVNS, and identify the transportation batches and customer groups of the product at the same time.In the process of iteration, crossover, mutation, neighborhood search and other operations are adjusted reasonably to avoid decoding confusion.Considering the need to optimize multiple objectives simultaneously in actual production, this paper aims at minimizing inventory holding cost, penalty cost in advance, penalty cost in time and transportation cost.The GA-OVNS is compared with the heuristic heuristic algorithm EDD(Earliest Due Data SLACKSlack Time rule and the intelligent optimization algorithm GAGA-VNS.The parameters of the hybrid intelligent optimization method are determined by orthogonal design.The experimental results show that the optimization performance of GA-OVNS is better than that of other algorithms.
【学位授予单位】：武汉大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TB497

【参考文献】