基于OCTPN和混合遗传算法的JSP多目标优化调度的开题报告.docx

基于OCTPN和混合遗传算法的JSP多目标优化调度的开题报告 一、研究背景及意义 作业车间调度问题（Job Shop Scheduling Problem，JSP）是一个经典的NP困难问题，它的基本形式是给定一组作业和一组机器，每个作业都需要在一组机器中依次加工，且每个机器同一时间只能加工一个作业。在JSP中，我们的任务是为每个作业规划一条机器序列，使得每个作业都可以按照序列依次加工，而且每个机器在同一时间只能加工一个作业。 近年来，多目标优化调度已成为研究的热点之一，因为在实际生产中，往往需要考虑多个目标，如完成时间、设备利用率、制造成本等等。针对JSP多目标优化问题，已经提出了许多算法，如NSGA-II、SPEA2、MOEA/D等等。然而，这些算法往往需要耗费大量的计算时间和内存，无法满足实际应用的需求。 因此，本研究旨在探索一种基于混合遗传算法和OCTPN的JSP多目标优化调度算法，以实现更高效、更精确的解决方案。 二、研究内容及方法 本研究的主要内容为： 1.设计一种基于OCTPN（Obtention de contre exemples par tranche de polyèdre numerique）模型的JSP多目标优化模型，将多个目标函数统一在同一个优化模型中，以实现更高效的求解过程。 2.提出一种基于混合遗传算法的JSP多目标优化调度算法，通过使用混合遗传算法来优化JSP多目标优化模型中的解，以提高求解效率和精度。 具体方法如下： （1）构建OCTPN模型 OCTPN是一种基于多项式边界算法的模型检验方法，可以将一个离散系统的行为特性表示为一个分段多项式函数的形式。在本研究中，我们将使用OCTPN来构建JSP多目标优化模型。 （2）设计JSP多目标优化模型 基于OCTPN模型，我们将设计JSP多目标优化模型，并将多个目标函数集成在同一个模型中，以便于求解。 （3）提出混合遗传算法 我们将提出一种基于混合遗传算法的JSP多目标优化调度算法，其中遗传算法用于求解JSP多目标优化模型，混合算法用于优化遗传算法的收敛速度和全局搜索能力。 三、研究计划及进度安排 本研究计划在以下时间段内完成： 2021.9-2021.12：阅读相关文献，学习OCTPN模型和多目标优化算法。 2022.1-2022.3：设计JSP多目标优化模型和混合遗传算法，编写实验代码。 2022.4-2022.9：进行实验验证，分析结果并撰写论文。 四、预期成果 本研究预期达到以下目标： 1. 提出一种基于OCTPN和混合遗传算法的JSP多目标优化调度算法。 2. 验证算法的效果和效率，并与已有算法进行比较。 3. 发表论文并参加相关学术会议。 五、参考文献 [1]贺琳琳, 陈龙城. 基于混合遗传算法的多目标JSP调度问题[J]. 工厂自动化, 2016(4):31-34. [2]杨乃立, 贾哲平. 多目标JSP问题的NSGA-II算法及其改进[J]. 计算机集成制造系统, 2019, 25(12):2967-2978. [3]Nanopoulos A, Papadopoulos C, Maris G. JSP scheduling with multi-objective genetic algorithms[C]//IFIP International Conference on Artificial Intelligence Applications and Innovations. Springer, Berlin, Heidelberg, 2008:81-88. [4]Jiang Y, Wang Y, Liu C, et al. An improved NSGA-II algorithm for multi-objective flexible job-shop scheduling problems[J]. Journal of Intelligent Manufacturing, 2018, 29(1):215-229.