一类单机器成组排序问题的算法研究

摘要

本文以现代生产制造业中成组生产为实际背景，研究了一类以最小化加权完工时间总和为目标(1|Sfg|∑wjCj)的成组作业生产排序问题。该问题在任意组别的情况下是NP-Hard难题，在大规模排序的情形下，将变得不可解，寻找最优解所需的计算时间将无法满足需求和生产多变的现代生产制造环境。因此本文将研究中心放在了该问题的近似搜索算法的研究上，本文的主要贡献主要于如下四点： 1.最优化模型的总结和延伸。生产作业排序的问题一直是学术界研究的焦点。针对成组排序问题也出现了一些理论成果，本文列举了现有的针对1|Sfg|∑wjCj问题的前向和后向动态规划算法以及该问题的一个重要的最优化排序性质，并给出了该问题的一个一般化的整数规划模型。 2.传统旅行商问题(TSP)的遗传算法的应用。最优化模型虽然从理论上可以求出1|Sfg|∑wjCj的最优解，但是其算法的复杂度为O(NF)，因此在大量组别的情况下，计算时间将变得不再可行。本文从TSP问题与排序问题的相似性出发，尝试将传统的用于解决TSP问题的遗传算法应用于1|Sfg|∑wjCj问题，给出了两种基因编码下具体的遗传算法的算子操作和算法流程。 3.一种新的遗传算法的提出。上述用于解决TSP的遗传算法没有考虑1|Sfg|∑wjCj自身的问题特征，因此本文尝试利用1|Sfg|∑wjCj的最优解集的特性，提出了一种新的基因编码(顺序编码)方式下的遗传算法(OGA)，该编码方式可以将染色体映射到一个较小的搜索空间，并且针对该编码设计了新的遗传算子，大大提高了搜索的效率。 4.三种遗传算法的实际算例结果比较。笔者对本文中的三种遗传算法用C++程序语言实现了其算法，然后进行了三个数据集的算例的计算测试，分别是50个工作10个工作组的数据集A、100工作20个工作组的数据集B和200工作和40个工作组的数据集C。

目录

文摘

英文文摘

第一章绪论

1.1引言

1.2制造业技术的发展

1.2.1成组技术(Group Technology)

1.2.2柔性制造系统(FMS)

1.3生产排序理论的发展

1.3.1排序问题

1.3.2生产排序问题的描述方法

1.3.3生产排序问题的复杂性

1.3.4生产排序问题的研究方法

1.4本文的研究背景

第二章单机器成组排序问题

2.1成组排序的模型描述

2.2带权完工时间总和的成组排序问题

2.3文献综述

2.4 1｜sfg｜∑wjCj的最优化模型

2.4.1重要性质

2.4.2动态规划模型

2.4.3整数规划模型

第三章单机器成组排序的遗传算法

3.1遗传算法简介

3.2遗传算法基本原理

3.3基本遗传算法(SGA)

3.4自然编码的遗传算法(NGA)

3.5顺序编码的遗传算法(OGA)

3.6计算实例

第四章结束语

参考文献

致谢

论文独创性声明及论文使用授权声明