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

摘要

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

目录

声明

摘要

第一章 引言

1．1．1 调度问题的研究背景

1．1．2 调度问题的基本描述

1．1．3 调度问题的基本分类

1．2 批调度问题

1．3 批调度问题的研究现状

1．3．1 单机环境下批调度闯题

1．3．2 多机环境下批调度问题

1．3．3 考虑拒绝成本批调度问题

1．4 论文研究内容与结构安排

1．4．1 论文的研究内容

1．4．2 论文的结构安排

第二章 批调度问题求解方法

2．1 确定性算法

2．2 启发式算法

2．3 元启发式算法

2．4 本章小结

第三章 考虑拒绝成本的多目标平行批调度算法研究

3．1 问题描述

3．2 问题下界和确定性求解算法

3．2．1 下界算法

3．2．2 确定性算法

3．3 基于ACO的元肩发式算法

3．3．1 解的编码

3．3．2 信息素的定义

3．3．3 启发式信息

3．3．4 候选列表

3．3．5 状态转移概率

3．3．6 机器选择机制

3．3．7 信息素的更新

3．3．8 解的构建

3．3．9 局部优化策略

3．3．10 算法描述

3．4 本章小结

第四章 仿真实验与结果分析

4．1 实验设计

4．2 参数设置

4．3 实验结果与分析

4．3．1 LACO算法的结果分析

4．3．2 PACO算法的结果分析

4．4 本章小结

5．1 总结

5．2 展望

参考文献

图目录

表目录

致谢

攻读硕士学位期间发表的论文

攻读硕士学位期间参加的科研项目