基于遗传算法的动态任务调度方法研究

摘要

任务调度问题是一个典型的NP-hard问题，作为一个前沿性的研究课题受到学术界的广泛关注，尤其是对具有现实意义的动态任务调度问题的研究更加具有理论意义和实用价值。 遗传算法（Genetic Algorithm，简称GA）是一种借鉴生物界自然选择思想和遗传机制的全局随机搜索算法。遗传算法最早由美国Michigan大学的J.H.Holland教授在二十世纪六十年代初借鉴了达尔文的生物进化论和孟德尔的遗传定律等基本思想，并将其进行提取、简化与抽象后，提出了第一个进化计算模型——遗传算法。并于1975年在其发表的《自然和人工系统的适配》中正式提出，标志着遗传算法的正式诞生。在该论文中，他称之为“Genetic Plans”，详细阐述了遗传算法的基本思想和结构框架。“Genetic Algorithms”一词首先出现在J.D.Bagley的博士论文中，他研究了遗传算法在博弈论（六子棋）中的参数搜索，这是遗传算法最早的应用。 遗传算法自1975年由Holland 教授提出其基本思想开始，就得到人们的广泛关注，相继提出了各种用于求解不同类型问题的遗传算法。通过大量研究得出结论，遗传算法在求解大搜索空间问题上具有独特优势，其受重视程度也日益增强。尤其在得到最优的任务调度方面，遗传算法体现了其有效性和最优性。本文重点介绍的遗传算法属于进化计算的范畴。进化计算是一种邻域搜索方法，是遗传算法、进化规则、进化策略和遗传编程的统称，是基于“适者生存”的一类高度并行、随机和自适应优化算法。各种算法的区别主要在于遗传操作的差别。进化计算的主要优势在于全局优化性，但其局部优化性却明显不足，因此有学者提出将进化计算与其他局部优化方法相结合使用，实践证明其局部优化性得到了提高。进化计算在人工智能领域有广泛的应用前景，国内对进化计算的研究自九十年代以来得到长足发展，各种论文、专著不断出现，并取得一定的成就。随着对进化计算认识的不断深入，进化计算的研究和应用必将取得更多的成果。 本文基于一般混合遗传算法的设计方法和mHEU算法，提出了一种混合遗传算法mGA，该算法利用mHEU算法对初始群体进行改进，评价产生的初始群体；再利用遗传算法对改进后的初始群体进行遗传操作，生成临时群体，然后二次利用mHEU算法对临时群体进行改进、评价；以此进行，循环反复，最终得到动态任务调度问题的解。本文提出的算法用任务的最小化最大完成时间（makespan）作为评价指标。 本文研究了遗传算法及其在动态任务调度问题中的应用，以遗传算法作为优化工具，提出了一种基于启发式方法mHEU算法和遗传算法的混合遗传算法mGA，以最小化makespan为优化目标，并对15个工件15台机器、20个工件15台机器、30个工件20台机器、50个工件15台机器、100个工件20台机器等5个不同规模的调度问题给出了计算机仿真结果，并与mHEU方法作了比较，结果表明所提混合算法mGA在最小化makespan方面优于mHEU方法，说明了该遗传算法在解决动态任务调度问题方面的有效性。本文的研究成果在动态任务调度方面有很好的效果，并为以后的研究工作打好了基础。 结合成熟的理论研究成果，以及本文所作的工作，现将本文总结如下：JSP调度是生产调度领域的典型代表，GA则是智能优化技术的代表，因此基于GA的JSP研究具有重要的理论意义和工程价值。随着对编码、特征分析、算法改进、比较、混合运算、推广问题、调度器开发和实际应用等有关问题研究的深入，该问题的重要性和受关注程度将会逐渐增强。然而，大量的工作还有待进一步深入研究和完善。 1．结合研究JSP的特性及其局部极小拓扑结构的分析和GA遗传算子的特性分析和结构设计，有助于更好地利用GA解决JSP问题，而这方面的研究目前还很少，不深入，因此对具有很强工程背景的代表性问题的研究是一个很重要的研究方向。同时，进一步开展GA的理论研究（如编码、参数选择、遗传算子设计、收敛速度估计、算法比较等），并利用数据挖掘、智能体等先进技术进行分析和研究，都能使我们更深入地认识GA，并推动其体系的发展，拓宽应用领域。 2．将JSP的数学模型更加现实化，动态调度的研究尤其值得重视，并将已有的理论成果推广到实际工程领域，用实践来检验技术的潜力，这不仅能够推动先进生产的发展，而且将促使优化技术的进一步完善。同时，鉴于生产技术人员对GA较陌生，开发相关的实用化、集成化调度平台和优化技术，具有很强的工程意义和实用价值。 3．鉴于国际学术界对混合系统与算法研究日益重视，混合优化策略以及相应的仿真环境的开发也将是一个值得关注的研究方向，尤其是将已有的各种调度方法的优点与GA有效地融合。 总而言之，随着计算技术、优化技术、数学理论和计算机硬件技术的发展，GA、JSP本身以及他们的结合研究将得到更加完善的解决，研究和应用领域更广，理论研究更加系统化、更接近于实际，并将朝着集成化、实用化、最优化、多目标化、动态化、规模化发展。5.2论文工作的小结及展望 本文在讨论动态车间任务调度求解算法的基础上，提出了一种车间作业调度问题的遗传算法和启发式方法结合的混合求解方法mGA。文中第四章详述了动态JSP问题的求解过程，并给出对TD类问题的几个子问题的仿真试验结果，通过与启发式方法mHEU比较，证实了混合遗传算法在动态JSP问题求解中的优势和全局搜索能力，其有效性尤其在大规模问题中特别突出。 本文主要有以下成果： 1．将文献[2]中提出的基于两台机器的可抢占的HEU算法加以改进，得到一种基于多台机器的可抢占的mHEU算法； 2．基于上述过程提出了一种基于GA和mHEU的混合遗传算法mGA，并应用在TD类问题上得出仿真结果。 本文虽然取得了上面提到的一些成果，但在以下几个方面仍有待进一步改进： 1．本文虽然采用Visual C++6.0编程，但是可视化程度不高，在以后的研究中需要提高程序的可视化程度，并同生产企业调度部门制订的调度计划实际联系起来研究，提高实用化程度。 2．本文在对动态JSP问题进行描述和求解时，将加工时间等时间参数假设为确定的，没有考虑时间参数的弹性和可变性。但实际生产过程中，各种随机因素（机器故障、工人操作的熟练程度、因故缺勤、环境变化等）的存在，时间参数的确定性很难保证，调度计划调度者提供的数据也受到各种实际情况的约束，不能保证面面俱到。在今后的研究要注意收集这方面的第一手资料，为进一步研究提供最原始的素材。 3．本文在仿真试验中所用数据为TD类问题的随机数产生方法，其对于动态调度问题研究的适用程度还有待进一步验证。并且，本文提出的混合算法还需要在比较成熟的仿真系统中去得到试验数据。

目录

第一章 引言

第二章 动态任务调度概述

第三章 遗传算法概述

第四章 遗传算法在动态任务调度问题中的应用研究

第五章 结论与展望

参考文献

附录

致谢