基于分枝定界的动态流水车间最大完工时间问题研究

摘要

在流水车间中，每个工件必须在不同机器上按照相同的加工路径进行加工，目标是确定使得目标函数最优的工件的加工序列，在任何时刻，每台机器至多可加工一个工件，且每个工件至多可在一台机器上进行加工，所有机器按照相同的机器顺序加工工件，当某个工件在某台机器上进行加工时，该过程不可以被中断。流水车间调度问题广泛存在于工业生产中，且大部分流水车间调度问题被证明是无法在多项式时间内求得最优解的NP难问题。即使是求解小规模的流水车间调度问题也是比较困难的。
　　本文针对三类动态流水车间调度问题，以极小化最大完工时间为目标函数进行了研究，分别提出了相应的分枝定界算法以获得小规模问题的最优解。最后通过数值实验仿真验证了算法的有效性。论文的主要内容概括如下:
　　首先，针对带有到达时间的流水车间极小化最大完工时间问题，提出对应的分枝定界算法，同时，提出分枝定界算法的分枝策略、剪枝规则、下界等。最后，通过数值实验进行仿真，将分枝定界算法与CPLEX软件中的算法进行对比，验证了分枝定界算法在解决带有到达时间的流水车间极小化最大完工时间问题时具有较好的性能。
　　其次，针对阻塞流水车间极小化最大完工时间问题，提出对应的分枝定界算法。同时，提出分枝定界算法的剪枝规则、下界等。最后，通过数值实验进行仿真，将分枝定界算法与CPLEX软件中的算法进行对比，验证了分枝定界算法在解决小规模的阻塞流水车间极小化最大完工时间问题时的有效性。
　　再次，针对带有学习效应的流水车间极小化最大完工时间问题，提出对应的分枝定界算法，同时，提出分枝定界算法的分枝策略、剪枝规则、下界等。最后，通过数值实验进行仿真，将分枝定界算法与CPLEX软件中的算法进行对比，验证了分枝定界算法在学习效应分别为线性函数、幂函数和指数函数时的有效性。
　　最后，总结了本文所做的主要工作，对未来的研究方向进行了展望。

目录

声明

摘要

第1章 绪论

1．1 调度问题

1．1．1 调度问题的描述

1．1．2 调度问题的表示方法

1．1．3 调度问题的分类

1．2 研究背景及意义

1．3 国内外研究现状

1．4 本文的主要工作及组织结构

1．4．1 本文的主要工作

1．4．2 本文的组织结构

第2章 相关知识介绍

2．1 相关定义

2．2 相关算法

2．2．1 分枝定界算法

2．2．2 DSJF启发式算法

2．2．3 SPTA启发式算法

2．3 优化软件CPLEX介绍

2．4 本章小结

第3章 流水车间极小化最大完工时间问题研究

3．1 引言

3．2 问题介绍

3．2．1 问题描述

3．2．2 数学规划模型

3．3 分枝策略

3．4 算法的下界

3．5 分枝定界算法

3．6 数值仿真实验

3．7 本章小结

第4章 阻塞流水车间极小化最大完工时间问题研究

4．1 引言

4．2 问题介绍

4．2．1 问题描述

4．2．2 数学规划模型

4．3 算法的下界

4．4 分枝定界算法

4．5 数值仿真实验

4．6 本章小结

第5章 带有学习效应的流水车间极小化最大完工时间问题研究

5．1 引言

5．2 问题介绍

5．2．1 问题描述

5．2．2 数学规划模型

5．3 学习效应函数

5．4 分枝策略

5．5 算法的下界

5．6 分枝定界算法

5．7 数值仿真实验

5．8 本章小结

第6章 总结与展望

参考文献

致谢

硕士期间发表的论文