具有分段恶化效应生产过程的智能优化调度研究

摘要

调度问题旨在将有限的资源分配给各项不同的任务，同时满足特定的需求和约束，其广泛存在于各类生产制造系统中。生产调度是制造系统中关键的决策过程之一，对其进行优化是车间管理的主要研究内容。采用合理的调度方案安排生产是提高制造系统作业效率的有效手段。在传统的生产调度问题中，通常认为工件的加工时间固定不变。然而在某些实际制造和服务过程中，工件的加工时间会因其开工时刻、加工位置的不同而发生变化，与传统调度问题相比生产过程具有恶化效应，由此产生了一类新的调度问题。该类问题中工件的加工时间由开工时刻、加工位置等因素的函数描述。若工件的加工时间由其开工时刻的分段线性函数和阶梯函数刻画，则称其具有分段恶化效应。此类问题较之传统调度问题更加复杂，绝大多数是NP-hard的，通常无法在合理的时间内求得最优解，对这类调度问题设计有效的调度优化方法具有重要的理论和现实意义。
　　本文研究了分段线性恶化和阶梯恶化这两类效应作用下的四个生产调度问题，给出了它们的复杂性分析。由于这些问题均是NP-hard的，难以在多项式时间内获得最优解，为此基于最优调度方案的结构特征和性质分析，设计了启发式调度优化算法。论文的主要研究内容有:
　　(1)研究了分段线性恶化效应作用下以最大完工时间最小化为目标的单机调度问题。此问题是强NP-hard的，无法通过多项式算法求解。在最优解的结构特征分析的基础上，提出了基于SPT排序规则的启发式算法DSPT-PI，同时引入了遗传算法以获得更高质量的解。该遗传算法使用DSPT和随机序列相结合的方式产生初始种群，采用线性顺序交叉算子和交换变异算子，并融入了成对互换搜索。基于随机数值算例的仿真结果表明，启发式算法DSPT-PI总体求解性能明显好于已有的启发式算法，遗传算法的求解精度优于模拟退火算法。
　　(2)对于具有阶梯恶化效应的单机调度问题，研究了总延误及总加权延误两种目标函数。针对该问题，建立了混合整数规划模型，证明了总延误最小化问题为NP-hard的，分析了最优解的性质，设计了基于修正交货期的启发式算法IMDD和简单加权搜索算法SWSP。同时还证明了总加权延误最小化问题为强NP-hard的，提出了通用变邻域搜索算法GVNS进行求解。利用随机算例对算法的性能进行了评估，分析发现GVNS能够有效地求解该问题，当求解大规模问题时给出的解的相对百分偏差为0.78％，相对平均偏差为0.81％。
　　(3)研究了具有阶梯恶化效应的并行机调度问题，构建了以总完工时间最小化为目标函数的混合整数规划模型，研究了不同建模方式下优化模型的求解效率。针对该问题，提出了改进加权组合搜索算法MWCSA，并设计了基于工件序列编码的变邻域搜索算法VNS。同时为了提高搜索速度，利用MWCSA为VNS产生初始解以形成改进算法VNS+MWCSA。基于随机算例的大量仿真结果表明，混合整数规划模型的求解效率依赖于恶化工期的取值区间，VNS+MWCSA算法的性能优于其他算法。
　　(4)研究了带调整时间和阶梯恶化效应的并行机调度问题，以最小化总延误为目标函数，建立了混合整数规划模型。针对该问题，提出了一种混合离散布谷鸟搜索(HDCS)算法。该算法采用基于工件排列的离散编码解码方案，在种群初始化过程中融合了启发式算法MBHG，在搜索过程中将种群划分为普通解集和精英解集，对普通解实施基于CS的离散搜索，对精英解实施基于变邻域下降的局部搜索。为了保持种群的多样性，对部分个体采用了Restarting策略。算例求解结果表明混合算法HDCS是十分有效的，其求解效率受恶化工期取值的影响极小。
　　本文针对分段恶化效应作用下的生产过程，以单机和同速并行机为加工环境，考虑了最大完工时间、总延误和总完工时间为优化指标的调度模型，并提出了相应的求解方法。本文的研究丰富了具有恶化效应调度问题的研究内容，拓宽了此类问题的求解途径，有助于推动生产调度理论的发展，具有重要的理论意义和积极的实际意义。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 传统调度问题

1．3 具有恶化效应的生产调度问题

1．4 具有分段恶化效应的生产调度问题

1．5 生产调度优化方法

1．5．1 传统运筹学方法

1．5．2 启发式规则调度方法

1．5．3 邻域搜索算法

1．5．4 智能进化算法

1．6 本文研究内容及技术路线

第2章 具有分段线性恶化效应的单机调度问题

2．1 引言

2．2 问题描述

2．3 启发式调度优化算法设计

2．4 改进遗传算法

2．4．1 遗传算法基本介绍

2．4．2 算法设计

2．5 算例仿真

2．5．1 算法参数设置

2．5．2 结果与分析

2．6 本章小结

第3章 交货期约束下具有阶梯恶化效应的单机调度问题

3．1 引言

3．2 问题描述

3．3 问题复杂性分析

3．4 启发式调度优化算法设计

3．4．1 启发式算法IMDD

3．4．2 启发式算法SWSP

3．5 通用变邻域搜索算法

3．5．1 初始化阶段

3．5．2 邻域搜索结构

3．5．3 随机及局部搜索

3．5．4 扰动搜索

3．5．5 算法框架

3．6 算例仿真

3．6．1 算例设计

3．6．2 结果与分析

3．7 本章小结

第4章 具有阶梯恶化效应的并行机调度建模与优化

4．1 引言

4．2 问题描述

4．3 混合整数规划模型

4．4 算例仿真

4．5 本章小节

第5章 具有阶梯恶化效应的并行机启发式调度优化方法

5．1 引言

5．2 启发式调度优化算法

5．3 变邻域搜索算法

5．3．1 编码、解码及初始化

5．3．2 邻域搜索结构

5．3．3 VNS算法框架

5．4 算例仿真

5．4．1 算法参数设置

5．4．2 结果与分析

5．5 本章小结

第6章 带调整时间和阶梯恶化效应的并行机调度问题

6．1 引言

6．2 问题描述及建模

6．3 混合离散布谷鸟搜索算法

6．3．1 编码解码方案

6．3．2 种群初始化

6．3．3 基于CS的搜索操作

6．3．4 局部搜索

6．3．5 Restarting策略与算法终止条件

6．3．6 算法框架

6．4 算例仿真

6．4．1 算例设计

6．4．2 算法参数设置

6．4．3 结果与分析

6．5 本章小结

结论与展望

致谢

参考文献

攻读博士学位期间发表的论文及参加的课题