论文部分内容阅读
带有等待时间约束的流水车间调度问题广泛存在于离散型车船制造生产系统、连续型石油化工生产系统和半连续半离散的混合型钢铁生产系统，其调度方法研究无论是在理论探索还是在实际应用中都倍受关注。本文以最小化最大完工时间或提前/拖期总费用为优化目标，对工序间带有等待时间约束的流水车间调度问题展开研究，着重系统地分析问题性质和深入地探讨符合问题特征的求解方法。主要研究内容和创新点如下：
(1)针对目标函数为最小化最大完工时间的无等待流水车间调度问题，建立了混合整数规划模型，提出了组合变邻域算法。在求解过程中，首先将问题转化为指派问题，以获得较好的初始解，然后利用块内块间变邻域搜索策略进行迭代，来改进解的质量。为了提高算法的搜索效率，在迭代过程中加入了禁忌策略。基于标杆算例的计算验证了算法的有效性。
(2)针对目标函数为提前/拖期惩罚最小，具有交货时间窗要求的无等待流水车间调度问题，建立了约束满足模型，提出了约束传播与邻域搜索相结合的求解方法。在求解过程中，首先使用嵌入约束传播的启发式方法产生初始调度，然后采用近邻的邻域交换结构进行迭代寻优，为避免陷入局部极值，迭代过程中采用多重交换邻域的扰动策略。
(3)针对工序间等待时间受限，目标函数为最大完工时间最短的流水车间调度问题，提出了一种动态变邻域搜索算法。算法采用工件对比较算法和贪婪插入，构建了初始调度；通过嵌入3-opt，2-opt实现动态变邻域搜索；并在迭代过程中加入动态禁忌策略。