论文部分内容阅读
随着工业生产规模不断扩大,需求日益个性化,市场竞争日趋激烈,对生产过程自动化的要求也随之逐渐增高。作为现代集成制造系统三层结构中的中间层制造执行系统(MES)也发挥着更加重要的作用,生产调度和执行是其核心组成部分。企业通过生产计划和生产调度,让有限的自身资源发挥更大的作用,产生更多的效益,从而提升企业生存能力和社会效益。生产调度是利用有限资源在一定时间内完成指定任务的决策过程。生产调度问题的研究是自流水车间调度问题而始。流水车间调度是其重要组成部分。 流水车间调度问题种类很多,绝大部分是NP难问题。传统的数学方法往往力不从心,使得启发式方法得到蓬勃发展,而元启发式算法由于其无需对问题本身建模,就能用黑箱方法求解;过程简便,适应性强,得到广泛的应用。近30年来,各种元启发式算法纷纷涌现。本论文从流水车间调度中的几个典型问题入手,在研究了问题特性的基础上,针对性地提出了几种元启发式算法对各问题分别进行求解。 (1)针对置换流水车间调度问题,提出了一种改进的多算子遗传算法(COGA,genetic algorithm with combined operators),用来求解其最小最大完成时间问题。在研究了各种交叉方式后,给出了一种环状交叉法。在此基础上讨论了交叉变异算子间的有机组合。本文提出的算法采用了一些启发式规则进行初始化,然后利用多种算子组合作为遗传操作,自适应的调整各算子组合的使用率,并采用精英保留的选择策略,然后通过对标准算例的仿真计算,与同类算法进行对比,结果显示多算子遗传算法具有一定的优越性。 (2)针对零等待流水车间调度问题,提出了一种基于NEH的启发式算法(NEHC),并用来求解其最小生产周期。依据该问题求解过程中的递推关系式,定义了前后相继加工的两工件间的距离,并以此作为依据进行排序得到初始序列。然后用NEH进行求解,过程中存在僵局情况的工件,则进入待定工件集合,再将待定集合中的工件进行重新插入,从而获得较优的调度解。然后通过对REC标准算例的仿真计算,与其他启发式算法进行比较,结果显示NEHC的寻优能力强于其余算法。 (3)针对阻塞流水车间调度问题提出了含有启发式规则的改进生物地理学算法(IBBOH)。首先根据阻塞流水车间调度问题的特性,给出了其生产周期的递推公式。采用两阶段启发式规则的方法改进了NEH规则,并用于本文算法的初始化。然后针对BBO算法易于陷入局部最优的问题引入了灾变操作,灾变操作中改变其按位操作的惯例,采用交叉变异的方式更新种群,并运用基于最大最小规则(MM)和轮廓适合规则(PF)的邻域搜索方法改进算法的寻优能力。仿真实验结果表明IBBOH算法性能有显著改善,优于同类算法。