调度问题广泛的存在于现实生活的各行各业之中,例如:机场飞机调度、海上船舶调度以及云负载均衡等诸多调度问题。这些调度类问题无一不是生产实践中的基础环节和核心问题。通过求解这些调度优化问题能够更好的帮助改进生产方式,提升生产效率,给人们的生产生活带来更多便利和实惠。然而,由于存在着大量具有NP难度的调度问题,同时现实生活中的这部分问题往往具有极其复杂的应用场景和海量的数据规模,因此求解它们无论是对学术界还是工业界来说都是具有挑战性难度的。随着近些年来启发式优化算法的不断发展,日趋成熟的启发式算法已经得到了研究学者们广泛的认可并且已经成为求解NP难问题非常有效的手段和工具。本文研究了调度领域中两个具有代表性的NP难问题即车间作业调度问题(Job Shop Scheduling Problem,JSP)以及卫星广播调度问题(Satellite Broadcast Scheduling Problem,SBSP),并为其分别设计了两种启发式优化算法。此外,通过计算实验对设计的算法性能进行了评估,同时分析以及讨论了算法中的重要参数和核心策略。本文的主要贡献包括:(1)通过引入基于最长公共子序列(Longest Common Subsequence)的交叉算符以及基于种群多样性管理机制的更新策略,提出了求解JSP问题的新的混合进化算法(Hybrid Evolutionary Algorithm,HEA)。此外,算法的对比实验证明了HEA算法的有效性,同时参数的分析实验说明了重要参数不同取值对HEA算法性能的影响。(2)针对JSP问题,本文提出了新的混合禁忌搜索和路径重连算法(Tabu Search&Path Relinking,TS/PR)。通过结合基于N7邻域结构的禁忌搜索以及自适应距离控制(Adaptive Distance-Control)的路径重连算法,使得整个算法能够在集中性和疏散性之间达到更好的平衡。算法的比较实验证明了TS/PR无论是在解的优度还是计算时间上都具有很大的优势和很强的竞争力。参数的分析实验说明了重要参数在TS/PR算法中的作用。(3)针对SBSP问题,提出了新的迭代局部搜索算法(Iterated Local Search,ILS)和混合路径重连算法(Hybrid Path Relinking,HPR)。ILS算法引入了基于0-slip动作的局部搜索过程以及基于1-slip动作的随机扰动过程。HPR算法将新提出的ILS算法与自适应距离控制的路径重连算法进行了混合。算法的比较分析实验说明了ILS算法和HPR算法的有效性。(4)在JSP问题中,将HEA算法与文献中两种先进的启发式算法(TS/SA和HGA)进行了对比。实验表明HEA算法能够匹配比TS/SA和HGA算法更多的最好解,同时HEA算法对于最好上界的匹配度高达90%以上。尤其是,HEA算法还能改进两个算例的当前最好上界。通过将TS/PR和文献中最先进的九种算法进行对比实验,实验结果表明TS/PR算法能够改进其中49个算例的最好上界,改进率高达64.88%。尤其是,TS/PR算法找到了具有挑战性难度的SWV15算例的最优解,是该算例提出20多年以来第一次找到其最优解。在SBSP问题中,将ILS算法和HPR算法与和文献中先进的四种算法进行了对比。实验表明ILS算法能够在短时间内找到质量不错的解,具有很好的实时性;而HPR算法能够找到更高质量的解,实现在解的优度和计算时间上更好的平衡。以上研究成果表明,本文提出的混合进化算法、迭代局部搜索算法以及混合路径重连算法都是求解对应调度优化问题的有效的启发式算法。通过本课题的研究,加深了对NP难度的调度优化问题的理解。根据本课题研究情况,总结如下:(1)结合求解问题的内在结构设计算法当我们在设计高性能启发式算法的时候,应该多根据求解问题的内在结构特点来导引算法的设计,尤其是邻域结构的设计。本文研究的两个组合优化问题,虽然都是调度优化问题,但是在设计邻域结构的时候,两个问题之间的邻域结构却是不能共享的。这是因为两个问题有着不一样的内在结构。从求解问题的解结构的角度来看,JSP问题本质上是一个排序类问题,而SBSP问题是一个分配类的0-1问题。针对排序类问题,较常采用的是基于“插入(Insert)”或“交换(Swap)”的邻域动作,而对于分配类的0-1问题,比如著名的可满足性问题SAT,翻转变元则是一种有效的邻域动作。因此在SBSP问题上,本文并没有借鉴JSP问题上邻域结构的设计方法,而是采用的翻转变元(卫星和终端之间的通信状态)的方式设计了基于0-slip动作的邻域结构。实验结果也证明了此方法的有效性。通过结合求解问题中的内在结构来进行启发式算法的设计是设计高性能启发式优化算法的关键。(2)混合算法的设计技巧基于混合算法的设计是近年来启发式算法的发展趋势之一。在设计混合算法的时候,应当尽量避免混合同类型的算法,尝试混合不同特性的启发式优化算法是更合理的选择。原因是启发式算法的设计过程往往是平衡算法集中性和疏散性的过程。当混合两种集中性都很强而疏散性都很弱的算法时,其产生的“木桶效应”便会显现。例如尝试将局部搜索算法和禁忌搜索算法混合的思路往往不切实际。因此在进行算法混合的时候,将两种不同类型的算法,尤其是优缺点互补的算法进行混合,往往能收获不错的效果。例如将局部搜索算法(或禁忌搜索算法)和群体算法进行混合。本文提出的ILS算法和禁忌搜索算法都是侧重于集中性的算法,而基于群体机制的进化算法和路径重连算法则是侧重于疏散性的算法。实验结果也证明通过将这些算法混合形成的HEA算法、TS/PR算法以及HPR算法能够在对应的求解问题上取得不错的效果。此外,在今后的研究中我们还将尝试利用这些算法去求解其它类型的NP难调度优化问题(或者组合优化问题)。