模糊环境下若干单机批加工调度问题的模型及其算法研究

摘要

调度问题是运筹学的一个重要分支，所研究的问题涉及到工农业生产、交通运输、城市规划、管理科学、电子加工业、通讯与网络技术、计算机科学与信息技术等诸多领域。从某种意义上讲，调度问题研究的就是将稀缺资源分配给在一定时间内的不同任务，它是一个决策过程，其目的是优化一个或多个目标。批加工调度问题研究的是如何把工件划分成子批，如何安排子批在机器上加工，使衡量排法好坏的目标函数为最小，这对于提高生产效率，改善服务质量有着重大的指导作用。本文试图在前人的研究基础上，主要研究模糊环境下的一些单机批加工调度问题，包括批容量问题、优先约束问题、交货期问题、加工时间问题，这些问题在现实中有着广泛的应用，如生产的组织、市场的管理、交通运输的安排，以及信息的处理等。本文所做的主要工作如下：
　　1.对批容量问题的一些模型进行扩充，提出两类批容量问题。第一类为批容量上限值固定的双目标单机批加工调度问题，考虑的双目标为：一是使得最大完工时间最小化；二是使得流程时间最小化；第二类为带有模糊批容量上界的三个目标函数单机批加工调度问题，这里的模糊批容量表示关于公共上界的满意度，考虑的三个目标为：一是使得对公共上界的最小满意度最大化；二是是使得最大完工时间最小化；三是使得流程时间最小化。对这两类问题，给出伪多项式时间算法进行求解。最后通过数值算例进行算法演示。
　　2.提出带有一般优先约束及清晰交货期的单机序列分批加工调度问题、带有模糊优先约束及清晰交货期的单机序列分批加工调度问题、带有一般优先约束及模糊交货期的单机平行分批加工调度问题以及带有模糊优先约束和模糊交货期的单机平行分批加工调度问题等四类关于优先约束和交货期的数学模型。这里的模糊优先约束反映对任务间优先次序的满意程度，模糊交货期使用隶属函数来描述决策者对工件完工时间相对于交货期的满意程度，优化目标就是最大化调度中的最小满意度。对这四类问题分别提出相应的求解算法，包括求解非支配解的算法，阐述算法的有效性并且给出算法的计算时间复杂度，最后分别通过数值算例进行算法演示。
　　3.提出带有模糊加工时间和清晰交货期的单机批加工调度模型。创造性地利用一种特殊的三角模糊数表示模糊加工时间。并首次提出批λ-N延迟这个新概念。完美地结合必然性测度理论对模糊数进行比较。在Moore算法的思想上给出新算法，来寻找由批数及每批中工件的分配组成的最优解来最小化总误工数，并满足每个批的批容量不超过共同的批上界的限制。说明算法的有效性和计算时间复杂度，最后通过数值算例进行算法演示，并以Matlab为平台，开发了模糊加工时间分批调度优化程序，证明了本章提出的算法时间复杂度的正确性，同时也验证了本程序处理复杂大数据问题的能力。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1模糊调度问题的研究背景及意义

1.2调度问题的分类与基本模型

1.3 相关批加工调度问题的研究现状

1.4 当前研究存在的主要问题

1.5 本文主要研究内容

第2章 带有模糊批容量的单机批加工调度问题

2.1 引言

2.2 关于批容量问题的一些模型

2.3 批容量上限值固定的双目标问题

2.4带有灵活批容量上界的三个目标问题

2.5 数值算例

2.6 本章小结

第3章 带有模糊优先约束和清晰交货期的单机序列分批加工调度问题

3.1引言

3.2 带有一般优先约束的问题

3.3 带有模糊优先约束的问题

3.4 本章小结

第4章 带有模糊优先约束和模糊交货期的单机平行分批加工调度问题

4.1引言

4.2 带有一般优先约束及模糊交货期的问题

4.3 带有模糊优先约束及模糊交货期的问题

4.4 本章小结

第5章 带有模糊加工时间和清晰交货期的单机批加工调度问题

5.1引言

5.2问题的描述与数学模型

5.3问题的解法

5.4数值算例

5.5本章小结

结论

参考文献

攻读博士学位期间发表的论文及其它成果

声明

致谢

个人简历