带有首工件选择策略的批调度算法研究

发布时间：2020-03-22 11:54

【摘要】：调度问题是一类具有广泛应用背景的组合优化问题,调度的主要目的是对有限资源的合理分配,以获得最大的经济效益。随着调度问题的复杂化,已经无法仅仅依靠经验来解决调度问题,这时候,一个高效的调度算法显得尤为重要。由于调度流程和环境的复杂化,调度问题不断多样化,且演化出多种具有不同特征的调度问题。其中,批调度问题就是对经典调度问题的扩展和延伸。批调度问题是将一定数量的工件同时使用批处理机进行加工的问题,广泛应用于多种场景,如物流运输、石油化工等。不同于经典调度问题,在批调度问题中一台机器可以同时对多个工件进行无中断加工。在批调度问题中,首先对工件进行分批,然后将工件以批的形式放入批处理机种进行加工。工件分批后,批的属性受该批中工件属性和加工该批的机器属性共同决定。批调度问题已经不满足于对单一目标的优化,逐步考虑到对多种互斥目标的优化,形成了多目标批调度问题。蚁群算法是一种根据蚂蚁觅食行为而提出的进化算法。不同于其他的进化算法,蚁群算法中的蚂蚁能够逐步构造问题的可行解。由于蚁群算法的构造性,近年来蚁群算法被广泛应用于批调度这一类组合优化问题中。蚁群算法通过信息素、启发式信息来指导蚂蚁构造新的可行解。在批调度问题中,信息素记录了工件与工件在同一个批中的历史权重关系,指导蚂蚁向历史优势解空间搜索。启发式信息通常是根据批调度经验所设计,指导蚂蚁向人们所期望的解空间进行搜索。通过信息素和启发式信息,有效降低了批调度问题的搜索空间,提高了解的搜索质量。本文首先研究了平行批处理机环境下,调度不同到达时间的差异工件,以获得极小化制造跨度的批调度问题。根据问题的特点,提出了一种新的下界算法以评价算法性能,并证明了本文所提出的下界算法是有效的。根据批构建过程中,第一个工件对于批构建过程的影响,对批构建过程中第一个工件的选择提出了弱约束标准和两个基于弱约束标准下的首工件选择策略,并将两个选择策略引入到蚁群算法中。仿真实验的结果表明,批构建过程中使用首工件弱约束策略是有效的且工件尺寸大的高概率选择策略优于平均概率选择策略。其次,研究了平行批处理机环境下,调度具有不同到达时间的差异工件,以获得极小化制造跨度和极小化最大延误的多目标问题。为了降低蚁群算法的搜索空间,针对批构建过程中的第一个工件提出了一种新的约束和选择策略,并设计了一种新的启发式信息。为了加强蚁群算法的局部搜索能力,引入了一种新的局部搜索蚂蚁P-ANT以加强算法在非支配解的邻域搜索能力。仿真实验的结果表明,本文所提降低蚁群搜索空间策略和新局部搜索蚂蚁是有效的。最后,对所研究的批调度问题与调度算法进行了总结,并对相关领域的研究方向进行了展望。
【图文】：

流程图,粒子群算法,蚁群算法,流程图

粒子通过当前位置和其速度矢量来移动每个粒子，以获得新的解。逡逑在粒子群算法中，主要的组成部分包括：目标函数、速度更新公式、位置更逡逑新公式和算法结束条件等。粒子群算法的算法流程如图２．２所示。逡逑初跳听＿子逡逑的位ｓ和速度逡逑逦ｙ逦逡逑计？所栜Ｌ逦逡逑子ｉｉ鹏值逡逑ｖ逡逑子的历灥尤枿逦男}逡逑否逡逑星否满足终止条件＾＞逦逡逑蝻出优彳七结逡逑ｍ逡逑（壀）逡逑图２．２粒子群算法流程图逡逑Ｆｉｇｕｒｅ邋２．２邋Ｔｈｅ邋ａｌｇｏｒｉｔｈｍ邋ｆｌｏｗ邋ｃｈａｒｔ邋ｏｆ邋ＰＳＯ逡逑２．３．３蚁群算法逡逑蚁群算法思想最早由Ｄｏｒｉｇｏ｜Ｍ１根据！ｌｉ１！蚁觅食ｆｒ为所提出，并很快得到逡逑者们的关注和研究。在寻找贪物T，蚂蚁eA初以随机的方式搜索巢穴周围的区域，逡逑１３逡逑

矩阵图,蚁群算法,信息素,矩阵

最初蚁群算法主要应用于旅行商问题｜５１］，并随着研宄的深入，蚁群算法己逡逑经用于多种组合优化问题，如作业调度１５２］、车辆路径问题［５３）等。蚁群算法的算逡逑法流程如图２．３所示。逡逑Ｃ＾Ｄ逡逑Ｉ逡逑初始化算法参数．逡逑送代次数设ｓ为0逡逑Ｉ逡逑逦？逆数增加逡逑Ｉ为每个幽构逡逑ｍｍ逡逑”逡逑计ｇ解适应度逡逑值逡逑更新信皂索逡逑—否达到薛大挪欠逡逑镝出优化结逡逑」［＿逡逑图２．３蚁群算法流程图逡逑Ｆｉｇｕｒｅ邋２．３邋Ｔｈｅ邋ａｌｇｏｒｉｔｈｍ邋ｆｌｏｗ邋ｃｈａｒｔ邋ｏｆ邋ＡＣＯ逡逑蚁群算法的核心是建立一个信息素系统，通常蚁群算法通过使用信息素矩阵逡逑来存储信息素。在路径问题中，，信息素通常代表一条路径到另一条路径的信息素逡逑浓度。蚁群算法的一些关键细节如下：逡逑（１）初始化信息素浓度：在蚁群算法工作的开始，首先将信息的浓度设置逡逑１４逡逑
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18;O221

【相似文献】