多约束多目标无等待混合流水调度建模与优化方法研究

No-wait flow shop scheduling problem is common in process industries and service industries, it is a typical NP-hard problem. Although no-wait flow shop scheduling problem has been studied systematically, a multi-objective no-wait hybrid flow shop scheduling with multi-constrain, which is more suitable for practical applications, has received few attentions from researchers. We will analysis the impact mechanism of complex constraints and multi-objective on traditional scheduling approach, and try to find some effective measures to handle them. Several typical constrains, such as parallel machines, changeover prohibition, skip stages, sequence-dependent setup times and precedence relationships among jobs are considered in this project. After analyzing the influences of them on scheduling operations, some idle matrix-based soft approaches are proposed, respectively. Then idle matrix-based scheduling modeling theory, which can handle above constrains, is presented. In addition, considering the important of preference, representation of preference, the fusion of preference and multi-objective, combination of permutation differential evolution with tabu search will be investigated, and a preference-based multi-objective permutation differential evolution algorithm will be proposed, it is used to solve multi-objective no-wait hybrid flow shop scheduling with multi-constrains effectively. Furthermore, simulation and comparison experiments will be conducted to illustrate the feasibility and effectiveness of proposed approach, and some improvement methods will also be suggested. This project will provide theory and technology for multi-objective no-wait hybrid flow shop scheduling with multi-constrain in real life, and it also has positive significance to improve and develop no-wait hybrid flow scheduling theory.

无等待流水调度问题广泛存在于流程企业和服务业中，是典型的NP难问题。目前针对无等待流水调度问题已有深入和系统的研究，但更能满足实际需求的多约束多目标无等待混合流水调度还未引起足够重视。本项目旨在分析复杂约束和多目标对传统调度方法的影响机制，提出有效的处理方法。包括：研究并行机、顺序关联的准备时间、禁止切换、先序要求和跳过处理单元等约束对调度操作影响的一般规律，分别提出基于空闲矩阵的软处理方法，建立能有效描述上述约束的基于空闲矩阵的调度建模理论；结合偏好信息，研究偏好的表示形式、偏好与多目标的集成方式和排列差分进化算法与禁忌搜索的结合机制，提出基于偏好的多目标排列差分进化算法，实现对多目标无等待混合流水调度的高效优化；开展仿真和比较研究，验证建模理论和优化方法的可行性和有效性，并提出改进办法。本研究将为实际无等待混合流水调度提供理论和技术支持，对推动和发展无等待混合流水调度研究具有积极意义。

任务调度问题广泛存在于生产实际中，是典型的NP难问题。现有任务调度研究主要是建立在对实际过程简化和理想状态假设基础上的，没有系统的考虑实际过程中的多种约束和多个目标需求。本项目旨在分析复杂约束和多目标对传统调度方法的影响机制，提出有效的处理方法，为实际任务调度提供理论和技术支持，对推动和发展复杂调度问题的研究具有积极意义。主要包括如下内容。.在任务调度方面：提出一种高效的基于任务聚类的成本感知工作流调度算法。提出的算法包括两个步骤：首先，基于时间考虑的垂直方向聚类，在垂直方向通过聚类顺序结构的细粒度任务来减少工作流的传输时间；其次，基于成本考虑的水平方向聚类，在水平方向通过聚类并行的任务，并且使用贪心策略为任务分配虚拟机和带宽资源，来实现截止时间内最小化费用的目的；最终可以获得满足在截止日期限制内最低费用的任务到虚拟机的调度组合；建立了一个能考虑异构性、截止期限、传输开销和成本的鲁棒性的任务调度模型，并提出了一种基于自学习策略和近邻启发机制的粒子群优化算法。此外，还设计了一种基于资源分类和任务优先级的启发式调度方法。算法对任务进行需求分类；根据用户对资源的渴求程度来计算任务的优先级；根据任务的优先级顺序以及用户任务的需求资源类型，贪心的调度任务到花费最小的虚拟机上。.在多目标优化方面：设计了一种基于多策略排序变异的多目标差分进化算法，该算法利用基于排序变异算子来快速接近真实的Pareto 最优解，同时引入多策略差分进化算子以保持种群的多样性; 通过自适应策略动态调整控制参数以提高算法的鲁棒性，并且从理论证明的角度分析了所提算法的收敛性。针对具有不规则真实Pareto前沿的高维多目标优化问题，提出了一种基于动态资源分配的高维多目标进化算法。算法采用切比雪夫方法将目标函数分解为一些子目标函数，并采用动态资源分配的方法，根据真实Pareto前沿的不同形状分配计算资源。此外，采用一种转换的密度评估方法对种群进行排序选择。