题目：鲁棒生产调度问题的建模与优化算法研究

实际生产中的各种不确定因素，如加工时间不确定、机器故障、急件到达等，经常干扰调度的实施，导致初始调度目标无法实现，各工件的开工和完工时间偏离初始调度，引起生产系统的混乱。鲁棒调度能够解决不确定环境下的生产调度问题，生成具有鲁棒性的初始调度。本文在已有研究的基础上，提出了鲁棒生产调度的一般性问题，总结分析了生产调度的鲁棒性指标及其测度方法，研究了加工时间不确定、机器故障和急件到达环境下的单机、并行机和Flow Shop鲁棒调度问题，建立了相应的鲁棒调度模型，给出了有效适用的算法，并进行了仿真验证。本文主要工作内容如下：1. 提出了鲁棒调度的一般性问题。总结了生产调度的不确定因素，归纳了鲁棒调度的相关术语，分析了调度鲁棒性与稳定性的联系和区别，构建了鲁棒调度的框架体系。在现有的生产调度鲁棒性指标与测度方法的基础上，给出了调度鲁棒性的统一的指标体系与规范的测度方法，并提出了一种新的调度鲁棒性的范数测度。2. 研究了加工时间为区间数的鲁棒生产调度问题。研究了以工期为调度目标，以工期偏差为鲁棒性指标的两台同速并行机鲁棒调度问题，建立了Min-Max准则的数学规划模型，设计了遗传算法与单机鲁棒调度启发式方法相结合的混合算法，仿真表明，本文的研究能够有效地解决该鲁棒调度问题。研究了以总完工时间为调度目标，以最大总完工时间偏差为鲁棒性指标的两台机器Flow Shop鲁棒调度问题，建立了Min-Max准则的数学规划模型，证明了给定调度的最大偏差必然存在于加工时间区间的端点，设计了分支定界与遗传算法结合起来的混合算法，使用遗传算法搜索加工时间，分支定界搜索调度方案，仿真表明，本文的研究能够有效生成总完工时间偏差较小，且性能损失很小的初始鲁棒调度。3. 研究了机器故障环境下的鲁棒调度问题。研究了以鲁棒性和最大延迟时间为目标的单机鲁棒调度多目标优化问题，在分别研究鲁棒性和最大延迟时间优化的基础上，提出了求解鲁棒性和最大延迟时间的Pareto解的方法，算例表明，本文的研究能够解决该多目标优化问题。研究了以工期为调度目标，以期望工期与工期偏差为鲁棒性指标的多台机器Flow Shop鲁棒调度问题，建立了以期望工期与工期标准差的凸组合为目标函数的数学规划模型，对基本量子进化算法进行改进，设计了一种变参数量子进化算法，并给出了与问题相符合的适应度函数，用于生成鲁棒调度，仿真表明，生成的鲁棒调度在机器故障环境下能够实现比确定性调度更满意的性能。研究了以工期为调度目标，以最大工期偏差为鲁棒性指标的两台机器Flow Shop鲁棒调度问题，依据干扰的结果将机器故障等效地转换加工时间的区间数，进而将该问题转换为区间数加工时间的鲁棒调度问题，仿真表明，本文的研究能够解决这样的鲁棒调度问题。4. 研究了带有急件到达的单机鲁棒调度问题。以总拖期为调度目标，以最大总拖期偏差为鲁棒性指标，建立了问题的模型，研究了相应的确定性调度问题的占优定理和占优规则，以此为基础，分析了急件到达对初始调度的作用，分析表明，急件到达没有改变原有工件的占优性，据此提出了鲁棒调度算法，算例表明，本文的研究能够生成总拖期偏差和性能损失都较小的鲁棒调度。