论文摘要
对于NP-完全问题,通常不能有效地求得问题的最优解,而是使用启发式算法在可接受的时间内找到问题的尽量好的解。车间调度（shop scheduling）问题具有约束性、非线性、多极小性、大规模性、多目标性等特点,一般属于NP-完全问题,目标解的搜索涉及解空间的组合爆炸。线性规划、分支定界等传统方法对于稍大规模的车间调度问题的求解无能为力,因此,通常使用启发式算法求解。车间调度是一个交叉性研究领域,吸引了运筹学、数学、管理学、决策学、自动化、计算机等领域的众多专家学者,同时,车间调度与控制技术是实现生产高效率、高柔性和高可靠性的关键,有效实用的调度方法和优化技术的研究与应用已成为先进制造技术的基础,因此研究求解车间调度问题的启发式算法有现实意义。本文研究了启发式算法在一类经典的车间调度问题——同顺序流水作业——中的应用,取得的主要研究成果如下:1.针对以最小化最大完工时间为目标的同顺序流水作业,在著名的NEH算法的基础上,提出了一个改进的构造性算法NEH-D。NEH-D算法主要从两点改进了NEH算法:首先使用一个更优的排序规则,在该规则中,不仅考虑了工件的总加工时间,而且考虑了这些加工时间的标准方差;其次,使用了一个消解插入冲突的策略。使用的优先规则有利于改进算法的性能;使用的消解插入冲突的策略对算法性能的改进起关键的作用。实验表明,NEH-D算法的性能优于NEH算法的性能,也优于最近提出的NEHKK算法和NEHKK1算法的性能;2.研究了求解目标为最小化最大完工时间的禁忌搜索算法的几个要素对算法性能的影响。结果表明提出的搜索策略对算法性能有较明显的影响,而提出的禁忌表结构、禁忌状态和不同的初始解对算法的性能没有明显的影响;3.针对以最小化总流程时间为目标的同顺序流水作业,提出了一个迭代局部搜索算法。该算法对初始解不是很敏感:当算法陷于局部极小时,需要对当前最优解做扰动并继续搜索,此时扰动强度对算法的性能有明显的影响。实验表明该算法的性能优于当前已有的算法,且该算法改进了90个基准问题中47个问题的当前最优解;4.针对求解最小化最大完工时间和总流程时间的多目标同顺序流水作业,提出了一个多目标局部搜索算法。针对两个目标,用现有的构造性算法牛成两个解,作为该算法的初始解,然后从这两个初始解出发,以贪婪的方式求出新的Pareto最优解集,持续改进Pareto前沿。选择新的Pareto解的条件是该解既不被原解支配,也不被产生原解的解支配,同时对某个目标改进最大。当所有的解都陷入局部极小时,扰动已得到的Pareto解集,然后从扰动后的解集出发重新搜索。初始解和选择新的Pareto解的方法对算法性能有显著的影响。在基准问题上,与文献中已有算法的比较结果表明提出的算法的总体性能更优,特别是对较大规模的问题,且此差异具有显著性。
论文目录
相关论文文献
标签：调度论文; 启发式算法论文; 元启发式算法论文; 多目标优化论文; 流水作业论文; 最大完工时间论文; 总流程时间论文;