【作者】 王林平；

【导师】 贾振元；

【作者基本信息】 大连理工大学 ， 机械电子工程， 2009， 博士

【摘要】 本论文主要研究齐套概念下的离散制造业生产调度问题。在多品种少批量或单件小批生产模式下,生产装配型制造企业生产管理中的关键问题之一就是缺件。齐套问题严重影响生产过程的同步进行。其次,以MRP为核心的管理信息系统,不能清楚反映不同工件之间的先后关系和产品齐套性,影响了制造业管理信息化软件的应用效果。第三,传统的生产调度研究,忽视了工件的可用性和订单的重要性。本论文主要研究面向齐套概念的两类基本调度问题:综合作业调度问题(CJSSP)和订单作业调度问题(COSPJS),主要目的是改善生产管理系统的性能以及提高客户对企业的满意程度。本论文的主要研究工作包括如下六个方面:(1)综述了齐套概念研究现状,在分析齐套概念内涵的基础上,给出齐套概念的定义,研究了齐套概念的应用,提出了面向齐套的生产调度模式。在综述含装配约束的调度问题研究现状、分析生产管理和调度理论研究中存在问题的基础上,提出了CJSSP概念,给出了三种分类方法,分析了CJSSP的涵义与用途。在系统描述CJSSP的基础上,建立了单产品和多产品问题的数学模型。(2)研究了在不可行域中求解CJSSP的遗传算法。在分析CJSSP特点的基础上,采用基于工序的扩展编码方案,提出基于选择解码字符串解码方法,从而给出了处理装配约束问题和不可行染色体的一种有效方法,对根据FT10构造的单产品和多产品CJSSP求解结果表明,遗传算法是可行和有效的。在总结遗传算法的基础上,提出了基于不可行域的CJSSP遗传算法概念,其关键技术是染色体转换方法。(3)提出了四种染色体转换方法。综述了约束处理技术的现状,提出了染色体转换的四项要求,设计并实现了四种转换方法,遗传算法应用实验说明了根右移子树归位法和基于路径表的扫描换位法转换结果最好,而且前者具有较好的综合性能。(4)提出了四种度量染色体转换质量的性能指标。在染色体语义分析的基础上,提出了染色体基因保位度、父项装配体基因右移量、父项装配体基因位移量和种群转换熵损失四种染色体转换度量指标,性能测试实验和遗传算法应用实验均得到了很好结果,证实了所设计定量指标的有效性。(5)研究了在可行域中求解CJSSP的遗传算法。在前面研究的基础上,提出了基于染色体转换的初始种群产生方法,采用分而治之的策略,综合应用编码方法和遗传操作算子来保证染色体的可行性,提出了装配体分类和可操作基因串两个核心概念,依此概念为基础设计了交叉与变异算子,对构造问题和文献实际问题的求解结果,以及与复杂规则算法结果的对比,证实了所设计遗传算法的优越性能。(6)研究了订单作业调度问题。综述了订单作业调度相关问题研究现状,提出了COSPJS概念,建立了COSPJS数学模型,提出了基于订单的交叉算子和变异算子,采用自适应交叉变异和基于相似性交叉技术,设计的遗传算法解决了普通遗传算法中解空间的适应值集聚难题,对较大规模的构造问题测试表明了算法的有效性。本论文研究表明,可以应用齐套概念有效解决离散制造企业广泛存在的缺件问题,CJSSP和COSPJS是面向齐套的生产调度的两类基本问题,不但具有理论意义而且具有实际应用价值,可以用遗传算法来求解这两类难题,从而得到优化的作业生产调度方案。更多还原

【Abstract】 The major intention of this dissertation is to research production scheduling in the discrete manufacturing underlying complete kit(CK).In high-variety low-volume(HVLV) or in one-of-a kind production(OKP) environment,shortage of components is the common things the machining-and-assembly type enterprises confronted with.It has strong impact on the synchronization of the manufacturing process.Moreover,the management information system(MIS) applied in enterprise centered by material requirements planning(MRP) did not provide the precedence relationship among jobs and the degree of product complete kit clearly, and this have already wakened the performance of the manufacturing system.Still further,the traditional production scheduling researches ignored the job availability and the importance of customer order.This dissertation researches two basic kinds of production scheduling problem toward complete kit:the complete job shop scheduling problem(CJSSP) and the customer order scheduling problem in job shop(COSPJS),with the motive to improve the performance of manufacturing system and enhance the satisfaction level of customers.The main research work lies in six aspects as follows.(1) The state-of-the-art of the literature concerning CK concept are surveyed.On the base of CK connotation analyses,CK terms are defined and CK application problem are traversed. Moreover,CK-oriented production scheduling paradigm is proposed.On the foundation of production scheduling overview involved assembly constraint and production theory analysis, this thesis put forward CJSSP concept.CJSSP are classified according three kinds,and its meaning and purpose are gathered up.Based on the systematic problem description,the single-product and multi-product model of CJSSP are established.(2) The infeasible search space based genetic algorithm(GA) for CJSSP are coined. The CJSSP features are explored.The extended operation-based representation is adopted in GA and the selective decoding string(SDS) is configured to deal with the infeasible chromosomes caused by the assembly constraint,therefore constraint-handling technique comes into being.The computation results indicate the feasibility and validity of the proposed approach using single- and multi-CJSSP adapted from the famous FT10 benchmark.The findings are summed up so that the feasible search space based GA are proposed.The infeasible chromosomes conversion technique is the key of it.(3) Four chromosome conversion approaches are suggested.The constraint-handling techniques are reviewed.Four conversion approaches are designed and realized based on the four requirements proposed for the conversion.Computational results indicate that all methods are viable in application,though different in speed and quality,and consistent with observation and GA application test results.Among them SLRRLS(subtree locus reversion based on root left shift) and CIP(circulatory interchanging based on pathway) are the best in quality,but the former executes rapider.(4) Four metrics for conversion quality are defined.Based on the semantic analysis of chromosome,four metrics:the gene position-preserving degree of chromosome、the gene locus right shift of parent constituents、the gene locus displacement of parent constituents and entropy loss of conversion population are designed.Both the performance tests and GA application results are conducted,the results differentiate the conversion approaches remarkably well so the metrics are confirmed convincingly.(5) The feasible search space based genetic algorithm(GA) for CJSSP are advanced. Based on the above-mentioned outcome,chromosome conversion based initial population construction is proposed.A divide-and-conquer strategy approach is adopted to maintain chromosome’s feasibility:operation-based representation overcomes the precedence constraints while genetic operators tackle the assembly constraints.Two core concepts, constituent type and operable gene string,are defined to build crossover and mutation.The genetic algorithm is tested on both practical instances and problems adapted from JSSP benchmarks.Comparison between the GA results and that of some sophisticated heuristics validated the GA to be the better.(6) COSPJS is studied.The literature of the customer order related scheduling problems are summarized.COSPJS is modeled mathematically.The self-adaptation crossover and mutation and the similarity-based crossover technique are adopted in the GA.They assist customer order-based crossover and customer order end shift that are created to overcome fitness value conglomeration,to solve COSPJS successfully.Large constructed benchmarks are used to test the performance of GA.The research results in this dissertation demonstrate that CK concept is very useful to deal with shortage of components widely existed in production management of discrete manufacturing.Both CJSSP and COSPJS are the two basic production scheduling problems towards CK.They are of importance theoretically and valuable in practice.Genetic algorithms are powerful to solve these two nearly intractable problems,so as to yield favorable schedules in job shop.更多还原