节点文献
一类离散制造业生产过程中的优化问题研究
Reaearch on Optimization Problem of Manufacturing Process in a Discrete Manufacturing Industry
【作者】 刘林;
【导师】 刘心报;
【作者基本信息】 合肥工业大学 , 信息管理与信息系统, 2009, 博士
【摘要】 生产调度和下料问题广泛存在于离散制造业的生产过程中,采用优化的生产调度方案安排生产是提高企业制造资源利用率的有效手段;而根据优化的配切方案进行下料是降低原材料消耗,提高企业竞争力的重要途径。当今离散制造业多品种小批量的生产方式决定了其生产调度和下料问题多为NP难题,通常无法在有效的时间内求得最优解,因此寻求近优解的方法被广泛地应用到实际的生产过程中。文章研究了一类离散制造业生产过程中的半flow shop等生产调度问题和多型材变截面一维下料问题,分别提出了改进的自适应混合遗传算法和两级分组启发式算法对问题进行求解,并将优化算法与信息系统的设计相结合,开发出了一个生产优化与执行系统。文章的主要贡献和创新点如下:1.在对马钢车轮公司火车车轮生产线的生产过程深入研究后,提炼出了一类离散制造业生产线生产方式中广泛存在的“半flow shop”生产调度问题,该调度问题类似于flow shop但又与flow shop有差别,它允许生产线上加工的产品可以跳过一些工序。文章根据实际生产情况建立了该调度问题的数学模型,并针对该调度问题的特点提出了一种用自适应遗传算法与FCFS调度规则结合求解的混合算法。2.提出了一种具有序依赖setup time的单机器批量生产调度问题,以总的setup time最小为目标建立了该生产调度问题的数学模型,设计了一种改进的自适应混合遗传算法求解该生产调度问题,对遗传算法的交叉和变异算子均按照该调度问题的特点进行了改进,提出一种“紧后任务选优重组交叉算子”,该算子能将调度排序上的优良性状很好地遗传到下一代群体中。用一种局部优化算法代替变异算子以提高算法的爬山能力。3.将一类使用多种型号圆台形原料的下料问题定义为“多型材变截面一维下料问题”。建立的数学模型考虑了刀缝宽度对切割计算的影响,考虑了企业生产的实际约束,并提出一种两级分组启发式算法对问题进行求解。4.在自适应遗传算法交叉和变异概率的计算中,引入基因信息熵的概念来计算个体差异度,克服了传统自适应遗传算法靠个体适应度来计算的不足,从而改善算法的性能。5.在小生境遗传算法中,对个体在群体中共享程度的评价方面,引入信息熵的概念,创造出了基于信息熵理论共享机制的小生境进化环境,维护了群体的多样性,改善了遗传算法的性能。6.将优化算法的研究成果应用到信息系统的设计中,设计开发了一类离散制造业生产优化与执行系统,并实现了与企业现有信息系统(如MES和ERP等)的无缝集成。并提出了一个基于MAS的生产调度与下料I3DSS结构框架。
【Abstract】 Scheduling problems and cutting stock problems exist in the production process of discrete manufacturing industry widely. It is an effective measure of increasing the utilize rate of manufacture resource that the production is arranged by the optimization scheduling. The important approach of reducing the waste of raw material, enhancing the competition ability of the enterprise is that cutting stock by the optimization scheme. Now most scheduling problems and cutting stock problems are NP-hard problems because of the production fashion of multi-varietal and small batch in discrete manufacturing industry. So it is impossible to discover the exact optimal solution in a valid time, therefore people have to find a near-optimal solution to some extent instead in practice. This paper research the specific scheduilng problems and cutting stock problems existing in the production process of a discrete manufacturing industry. The improved adaptive hybrid genetic algorithms are proposed to solve the scheduling problems, and a two-phase heuristic algorithm is proposed to solve the cutting stock problem. The fruits of the research have been employed to design the production system. A optimization production and execution system is made. Concrete research the contents is as follows:1. A semi-flow shop scheduling problem is proposed after the research on manufacturing process of the production line of train wheel in Masteel Wheel Company. This scheduling problem is similar to flow shop scheduling problem, but it is different from the flow shop scheduling problem. The jobs are allowed to pass some working procedures in the production line. The math model of this scheduling problem is upbuilt according to the real production case. A novel hybrid algorithm that combines the improved adaptive genetic algorithm with FCFS scheduling rule is proposed for solving this scheduling problem.2. A single machine scheduling problem with batchs setup time depending on sequence is proposed. The math model to minimize setup times is upbuilt. An improved adaptive hybrid genetic algorithm is brought up for solving this scheduling problem. Several operators are redesigned according to the characteristic of this scheduling problem. Follow job optimization recombination crossover is advanced for transmitting the good character to the offspring. To improve the mountain climbing ability of the genetic algorithm, the mutation is replaced by a local optimization algorithm. 3. The shape of the material used for cutting is frustum of a cone in Masteel Wheel Company. And the material has various types. This cutting stock problem is defined as one dimensional, multi-type and variable-section material cutting stock problem. In this paper, the influence of cutting slot on calculation is considered. Optimization model will be discussed in real production constraints, and propose a two-phase heuristic algorithm to solve the problem.4. The concept of gene entropy is used for calculation of adaptive probabilities of crossover and mutation, making the measures of the diversity of the population more accurate, so as to improve the performance of the algorithm.5. In the niche genetic algorithm, the concept of entropy is employed to measure the extent of individuals sharing. The niche evolution entironment is set up to suppress the similar individuals to maintain large diversity of the population, improve the capability of the algorithm .6. In Masteel Wheel Company the production optimization and execution system is designed through combining optimization decision theory, optimization algorithm with information system. This system is integrated seamlessly with existent information systems (such as MES and ERP). In addition, a structure of optimization scheduling and cutting stock I3DSS is designed based on MAS.
【Key words】 cheduling; cutting stock; genetic algorithm; entropy; heuristic; information system;