论文摘要
单机调度问题(Single Machine Scheduling,SMS)是一类重要的生产调度问题,在理论上,单机调度可看作是其它调度问题的特殊形式,是复杂的多机调度系统的一个子系统,深入研究单机调度问题可以更好地理解复杂调度系统的结构。在生产实践中,复杂调度问题往往可以分解为多个单机问题来解决。单机调度问题也是一类经典的NP难题,对单机调度问题求解算法的研究可以提供求解复杂调度问题的算法基础,因此,设计一种简单高效的求解算法是单机调度问题研究的重要方面。蚁群算法(Ant Colony Optimization,ACO)是一种智能启发式算法,受自然界中真实蚂蚁觅食行为启发而来,在信息素的帮助下,蚁群在觅食时总能够找到最短路径。蚁群算法的解构建程序是在搜索过程中通过不断向部分解添加符合定义的解成分从而构建出一个完整解,从这个意义上说,单机调度问题多阶段决策的属性非常适合蚁群算法求解。而且,蚁群算法具有系统性、自组织性、分布式计算、正反馈等特点,使得它在理论上比其它算法求解单机调度问题时有更大的优越性。但在实际应用中,蚁群算法也出现了运算时间较长、容易陷入局部极小、参数选取过程比较复杂、算法的智能化程度(自适应能力)较低等缺点。因此我们提出了进一步改善蚁群算法性能的策略与技术,发展了求解单机调度问题的改进蚁群算法。本文以一类单机调度问题为研究对象,以设计求解该类问题的有效算法为研究重点,提出了求解单机加权延迟调度问题的几种改进蚁群算法。具体的说,本文的主要内容及创新点包括:1、首先指出了论文所要研究的单机调度问题的概念及其研究背景,并从理论研究和生产实践两方面分别阐述了研究单机调度问题的意义;接着给出了单机调度问题的理论模型和结构图,建立了一个具有一般意义的基于模块设计的蚁群算法流程框架;然后提出了本文所要研究的单机调度问题的特征,从理论上分析了蚁群算法求解单机调度问题的可行性和具有的优势;最后对包括单机调度问题、单机加权延迟调度问题和蚁群算法等相关问题的研究现状进行了简要的分析总结,提出了存在的问题,指出本文的研究重点是设计适合求解SMTWT问题的蚁群算法。2、从蚁群算法功能模块的角度在方法层面和理论层面总结了蚁群算法的设计思路,分析了蚁群算法的不足,由此提出了分支蚁群动态扰动算法(DPBAC算法),从以下五个方面对基本蚁群算法进行了改进:引入分支策略选取初始出发城市;对状态转移规则进行了改进;引入交叉变异策略改进蚂蚁周游路径;改进信息素更新规则,引入信息素交流策略中和蚂蚁信息素的差距;引入条件动态扰动策略进行分阶段局部搜索,等等,并且对DPBAC算法的收敛性进行了证明。实验表明,该算法可以有效改善基本蚁群算法搜索时间较长、容易陷入局部极小等缺点,并且与其它类型的蚁群算法相比也有一定的优势。3、研究了求解一类强NP难的单机调度问题——单机加权延迟调度问题(SMTWT)的蚁群算法。首先从一般意义上给出了SMTWT问题的变量定义和数学模型,并从附加约束、启发式规则和求解算法等方面对近年来关于SMTWT问题的研究文献进行了综述,然后基于DPBAC算法的设计思想提出了一种求解SMTWT问题的改进蚁群算法AC SMTWT,并针对SMTWT问题的特征做了相应的改进,包括选用EDD(Earliest Due Date)规则产生问题的初始解,采用信息素累加规则计算状态转移概率,构建两两交换(interchange)邻域和插入(insertion)邻域进行局部搜索,运用信息素中和策略消减各节点间信息素之间的差距,等等,并且结合算法的搜索机理从理论上推导了算法的参数值。通过大量标准数据实验表明,AC SMTWT算法在计算结果和计算时间方面均优于遗传算法,而且与其它蚁群算法相比也有一定的优势。4、针对AC SMTWT算法在求解SMTWT问题的过程中参数选取过于复杂这一问题,提出了基于Q学习蚁群算法的SMTWT问题求解模型。首先,建立了单机加权延迟调度的多阶段决策问题模型,推导了SMTWT问题的Markov性。其次,分析了蚁群算法的Markov性,在Q学习理论框架下对蚁群算法的流程进行了解释。再次,对Q学习在单机调度研究中的应用进行了综述,分析了用查找表方法计算Q函数的不足,在此基础上建立了一个BP网络模型对Q函数进行估计。最后,将Q函数的环境无关性、Agent的学习能力和蚁群算法的分布式计算、正反馈等优点相结合,建立了基于AC_Q算法的SMTWT问题求解模型。实验表明,AC_Q算法在计算性能上与AC SMTWT算法基本相当,但对问题参数的依赖度更小,智能度也更高。总之,单机调度问题研究不仅在理论上还是在实践中都有重要的意义,由于单机调度问题是NP难问题,因此对它的求解算法的研究非常重要。在本文中,首先提出了一种适用于一般组合优化问题的改进蚁群算法——DPBAC算法,在此基础上设计了一种求解SMTWT问题的改进蚁群算法AC SMTWT,而为了解决AC SMTWT算法参数选取复杂、蚂蚁智能化程度较低等问题,又提出了基于Q学习的改进蚁群算法AC_Q,并建立了基于AC_Q算法的SMTWT问题求解模型。可见,本文的研究内容是相互联系自成体系的,本文的研究成果为单机调度问题的研究提供了一些新的理论和方法,同时也拓展了蚁群算法的理论研究和应用研究的领域。
论文目录
相关论文文献
标签：单机调度论文; 蚁群算法论文; 问题结构图论文; 功能模块论文; 单机加权延迟调度问题论文; 多阶段决策问题论文; 学习论文; 网络论文;