蚁群优化算法在带有拒绝的多目标批调度问题中的应用研究

• 作 者: 裴明丽
• 出 处: 安徽大学
• 发表日期: 2004年期
• 关键词: 多目标优化 蚁群优化 批调度 制造跨度 拒绝成本

调度问题是一类极其特别且多元化的组合优化问题,广泛应用于生活中的各个方面,如物流、加工制造业等。研究调度问题的主要目的是合理分配有限的资源,使得资源在分配过程中井井有条,提高生产效率,为企业带来更多的利益。然而随着生产规模的不断扩大,调度问题变得越来越复杂,为了改善企业的经营状况,出现了一种新型的调度问题——批处理机调度,简称批调度。批调度问题与传统的经典调度问题主要区别是在同一时刻上,多个工件可以被同一台机器同时加工,即多个工件以批的形式在机器上加工,其加工时间等于批中所有工件的最大加工时间。由于受工件属性、机器属性以及目标函数的影响,使得批调度的问题是非常复杂的,即使在单机环境下,也被证明为是一类NP难问题。为了解决这样的难题,很多国内外的专家和学者开始寻找效率更高的求解方法。另外,企业为了减少生产时间,必须拒绝加工某些工件,因此需要付出一定的代价,即产生了拒绝成本,本文的研究目标是最小化制造跨度和总的拒绝成本。首先,介绍了批调度问题的研究背景,描述了三参数表示法中的相关内容,再介绍了批调度问题的研究现状,包括单机、多机以及考虑拒绝成本的批调度问题。第二,介绍了求解批调度问题的三大类算法,分别是确定性算法,启发式算法与元启发式算法。第三,基于蚁群优化(ACO)算法,提出了 LACO与PACO两种算法分别解决线性组合和基于Pareto的非支配解两个多目标优化问题。另外,详细介绍了LACO算法与PACO的共同部分,如双信息素矩阵的定义,双启发式信息的定义等,也介绍了其不同部分。第四,描述了实验中参数的设置,测试实例的生成,然后统计实验数据,并将本文提出的算法得到的实验结果与其它对比算法进行比较和分析,进而得出相关结论。最后,总结本文的研究内容,并进行展望。