考虑批设置时间和模具数量约束的平行机调度——启发式算法及应用

摘要

平行机调度问题，是一类比较难的调度问题，在现实世界有广泛的应用，并在学界和业界进行了广泛而深入的研究。本文从一家典型的制鞋企业实际生产问题出发，将其归结为一类考虑设置时间和模具数量约束的一致平行机调度问题。具体可以表示为问题，其中代表同速平行机，考虑不同产品之间非顺序依赖的批设置时间，表示需要考虑模具数量约束。代表目标是完工时间。 本文就建立了整数规划模型，提出了最少拆分次数（Least Splitting Times，LST）、最少闲置时间（Least Idle Time，LIT）最大剩余任务优先（Most Jobs Remaining first，MJR）和最大剩余可用时间优先（Most Available Time first，MAT）、合并插入优先于底部插入，底部插入优先于顶部插入等4条优化规则，并在此基础上提出了预分批（Pre-partitioning）机制、安排（Allocation）机制、平衡（Balancing）机制、模具数量约束保证机制等调度机制。并在此基础上提出了启发式算法的基本架构。 本文利用优化规则和调度机制，针对该问题提出了LSTE（List Scheduling and Try-and-Error Heuristic）算法、PLSS（Partitioning and List Scheduling Heuristic）算法和MLSS（Modified List Scheduling and Splitting Heuristic）算法3种算法。对3种算法的实验结果表明，LSTE算法的求解质量最佳，虽然计算时间较长但可接受。而MLSS算法则在求解质量和运算速度方面均有一定的优势。而LPT算法虽然是经典的算法，在考虑模具约束的调度中，往往是失效的。预分配机制相对求解质量有一定程度的提高，但会造成计算时间的大量增加。实际的生产案例也得出了类似的结论，验证了LSTE算法的有效性。本文给出一个最短制造期的下界，实际中，这个下界很接近这保证了LSTE算法可以在更短的时间内找到最优解或近优解。文中还对LSTE算法的可行性进行了论证。

目录

声明

1 绪论

1.1 研究背景

1.2 问题描述

1.3 国内外研究现状

1.4 研究目的和意义

1.5 研究内容及方法

1.6 论文框架

2 问题描述与建模

2.1 问题描述

2.2 建立数学模型

3 启发式算法的提出

3.1 最优完工期的界定

3.2 启发式算法的思路

3.3 两种基本的算法

3.4 三种优化算法的提出

4 算法验证及结果分析

4.1 计算仿真实验设计及结果分析

4.2 应用在实际注塑机组排程问题的结果分析

5 结论与展望

5.1 主要结论和创新点

5.2 局限和展望

参考文献

致谢