应用齐套概念的离散制造业生产调度问题研究

摘要

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

目录

文摘

英文文摘

声明

1绪 论

1.1研究背景

1.2生产调度问题研究现状

1.2.1生产调度问题分类

1.2.2生产调度问题的特性

1.2.3生产调度理论发展历程

1.2.4生产调度问题研究方法与技术

1.3论文主题相关概念

1.4齐套概念应用研究现状

1.5论文研究主题及其来源

1.5.1本文研究的主要问题

1.5.2问题来源

1.6论文主要研究工作及其结构

1.6.1研究意义

1.6.2论文研究思路

1.6.3主要研究工作

1.6.4论文组织结构及内容

1.7本章小结

2齐套概念与CJSSP模型的建立

2.1引言

2.2齐套概念及其应用

2.2.1齐套概念

2.2.2齐套概念应用

2.2.3企业调研情况

2.2.4齐套概念应用模式

2.3含装配约束的调度问题研究现状

2.4综合作业调度问题的提出

2.4.1生产调度研究与应用中的缺陷

2.4.2提出综合作业调度问题的原因

2.4.3 CJSSP概念

2.5 CJSSP分类及特点

2.5.1 CJSSP分类

2.5.2 CJSSP特点

2.6单产品CJSSP的概念与模型

2.6.1单产品CJSSP描述

2.6.2单产品CJSSP数学模型

2.7多产品CJSSP的概念与模型

2.7.1多产品CJSSP描述

2.7.2多产品CJSSP模型

2.8本章小结

3基于不可行域的CJSSP遗传算法

3.1引言

3.2遗传算法原理与特点

3.2.1遗传算法简介

3.2.2求解调度问题的编码方案

3.2.3适应值函数的构造

3.2.4遗传算法的特点

3.3单产品CJSSP遗传算法

3.3.1 CJSSP问题分析与约束处理策略

3.3.2编码方案

3.3.3初始种群的产生

3.3.4选择方法

3.3.5适应值函数

3.3.6交叉与变异操作

3.3.7解码方法

3.4单产品计算结果与分析

3.4.1实验环境及其结果

3.4.2实验结果分析

3.5多产品CJSSP遗传算法

3.5.1编码设计

3.5.2交叉与变异操作

3.5.3遗传解码方法

3.6多产品计算结果与分析

3.6.1实验结果

3.6.2实验结果分析

3.7基于不可行域的CJSSP遗传算法

3.7.1单产品与多产品遗传算法总结

3.7.2不可行域遗传算法的关键技术

3.8本章小结

4不可行染色体转换方法及其性能度量指标

4.1不可行解及其转换概念

4.2遗传算法与约束处理技术

4.3约束处理技术研究现状

4.4不可行染色体转换要求

4.5转换方法设计

4.5.1基于SDS的多遍扫描(CSSDS:Circulatory Scanning based on SDS)

4.5.2基于依赖矩阵的回退扫描(CSRDSM:Circulatory Scanning with Reciprocation based on DSM)

4.5.3基于路径表的扫描换位(CIP:Circulatory Interchanging based on Pathway)

4.5.4基于根右移的子树归位(SLRRLS:Subtree Locus Reversion based on Root Left Shift)

4.6转换方法试验结果与分析

4.6.1转换速度实验

4.6.2遗传算法应用实验

4.7转换性能指标设计

4.7.1染色体语义概念

4.7.2染色体基因保位度

4.7.3父项装配体基因右移量

4.7.4父项装配体基因位移量

4.7.5种群转化熵损失

4.8性能指标测试结果及其分析

4.8.1转换速度实验

4.8.2染色体基因保位度实验

4.8.3父项装配体基因右移量实验

4.8.4父项装配体基因位移量实验

4.8.5种群转换熵损失实验

4.9染色体观察与遗传算法应用实验

4.9.1染色体观察

4.9.2遗传算法应用实验

4.10本章小结

5基于可行域的CJSSP遗传算法

5.1调度问题遗传操作算子

5.1.1交叉算子

5.1.2变异算子

5.2 遗传算法设计

5.2.1分而治之策略

5.2.2算法概述

5.3初始种群产生方法

5.3.1直接生成法

5.3.2可派工集法

5.3.3染色体转换法

5.4装配体分类概念

5.5可操作基因串概念

5.6交叉与变异算子设计

5.7实验测试结果及其分析

5.7.1 Benchmarks测试结果及其分析

5.7.2实例问题测试结果及其分析

5.8本章小结

6订单作业调度问题及其遗传算法

6.1引言

6.2订单作业调度问题概念

6.2.1调度理论中的订单

6.2.2订单作业调度问题概念

6.3订单作业调度相关问题研究现状

6.3.1经典调度问题与订单调度

6.3.2订单调度及相关问题研究现状

6.4 COSPJS模型

6.4.1 COSPJS描述

6.4.2数学模型的建立

6.5 COSPJS遗传算法

6.5.1编码

7.5.2产生初始种群

7.5.3适应值函数

7.5.4选择操作

7.5.5基于订单的交叉算子设计

6.5.6基于订单的变异算子设计

6.5.7基于相似性的交叉控制

6.5.8交叉与变异自适应参数

6.5.9染色体解码

6.6遗传算法结果与分析

6.6.1实验测试问题

6.6.2实验结果及其分析

6.7本章小结

7实例与应用

7.1企业基本情况

7.2管理信息系统介绍

7.2.1汽车转向器公司

7.2.2减速机公司

7.3齐套查询算法与应用

7.4 CJSSP实例

7.5本章小结

结 论

展 望

创新点摘要

参考文献

附录A两个JSSP基准问题

攻读博士学位期间参与的科研项目及发表学术论文情况

致 谢