论文部分内容阅读
生产调度是现代制造业管理的关键和核心技术,优化的生产调度方案能够使企业获得最大的经济效益和社会效益,因此,对生产调度的研究有着重要意义。在以往的研究中,大部分学者研究确定性调度问题,然而,在实际的生产过程中,往往存在大量事先无法预料的不确定因素,例如,生产设备发生故障、任务的处理时间发生变化、产品的需求量不确定以及其他不确定事件。因此,必须考虑不确定情况下的生产调度,在保证生产过程合理、正常运行的前提下,使企业获得最大的效益。本文针对不确定生产调度问题,采用随机规划理论建立几类生产调度问题的数学模型;为了解决随机调度模型的优化的复杂问题,提出了几种改进的量子进化算法和协同进化算法,并将其应用于随机调度,给出了几类随机调度的算法。论文的主要贡献如下:
(1)针对带提前/拖期指标的随机并行机调度问题,建立了成本期望值最小的随机并行机调度模型,其中加工时间为随机变量,服从均匀分布,并采用量子算法进行优化。为了克服量子遗传算法容易早熟收敛的问题,提出一种新颖的多宇宙量子遗传算法,该算法借鉴了多宇宙学说的基本思想,在搜索后期实施量子多宇宙策略进行精搜索。随机调度的数据仿真结果表明多宇宙量子遗传算法比遗传算法和量子遗传算法效果更好。
(2)针对随机Job Shop问题,建立了随机期望值规划模型,其中加工时间独立同分布于正态分布。提出了并行量子遗传算法对该调度问题进行求解,该算法是基于并行进化思想和量子理论的相关概念,模拟了一种并行的量子计算模型。在该模型中,存在多个子种群,几个子种群为一组,称为“宇宙”。在宇宙内部,所有的子种群形成超星型网络拓扑结构,子种群之间实施一种新颖的渗透迁移策略来自适应的控制个体的迁移方向和迁移数量。在宇宙之间,实施量子交叉策略。根据Job Shop调度编码的特点,专门设计了编码策略,将量子位编码转换到Job Shop编码上,同时设计了相对大角度的量子旋转角度查询表。实验仿真结果验证了NPQGA算法的有效性和实用性。
(3)针对随机Job Shop问题和带并行处理单元的随机Flow Shop调度问题的复杂性,提出了灾变式合作协同遗传算法和竞争型协同量子遗传算法进行求解。变式合作协同遗传算法主要针对基本合作式协同遗传算法容易陷入局部最优的弊端进行改进,当种群出现趋同现象时,就执行灾变操作,原有基因的垄断性优势被打破,从而增加了基因的多样性,激发出更好的基因。大量仿真结果验证,改进对算法有一定的改善作用。竞争型协同量子遗传算法是基于多种群协同进化思想和量子理论的相关概念提出的。在种群进化过程中,我们提出三种新策略—竞争捕食策略、协同合作策略和大鱼吃小鱼策略,通过判断多种群之间的相互作用程度来动态调整种群规模,提高了种群的自适应性。同时还设计了新的调度编码转换机制和量子种群更新操作。实验结果显示了竞争型协同量子遗传算法较好的可行性和有效性。
(4)研究了带设备故障的两种随机调度问题—随机Flow Shop问题和带并行处理单元的随机Flow Shop问题,不仅加工时间是随机变量,而且设备故障的发生时刻和设备修理时间也是随机变量。在随机Flow Shop问题中,分析了两种故障模型preemptive-resume model和preemptive-repeat model,每种模型下又讨论两种故障情况:故障发生后,任务的加工时间是否重新采样。在带并行处理单元的随机Flow Shop调度问题中,针对故障可能发生的不同情况(故障发生在加工任务的正常加工时段或者设备空闲时段),给出相应的仿真求解方法,即计算相应情况下加工任务的起始加工时间和完工时间。在调度优化算法方面,将量子理论和协同进化计算相结合,提出了一种合作型协同量子遗传算法进行求解,实验仿真结果显示了算法的优越性。
(5)针对不同中间存储方式的随机Flow Shop调度问题,分别建立具有零等待和有限中间存储的随机期望值规划模型,并用量子遗传算法进行求解,仿真结果验证了所建的调度模型和量子遗传算法的有效性。