2020年春季学期，一场突如其来的疫情，阻挡了员工们返校的脚步，影响了2020届毕业生毕业设计（论文）进展。为做好毕业设计（论文）指导工作，学院多次召开线上会议，研讨毕设线上指导工作，制定《437必赢会员中心2020年春季学期防疫阶段本科毕业设计实施方案》、《437必赢会员中心2020年春季学期防疫阶段本科毕业设计相关要求》、《437必赢会员中心关于开展2020届本科生毕业设计（论文）中期检查方案》。毕设指导教师积极完成毕设员工情况梳理，并根据员工实际情况进行分类指导，利用“云端”开展线上毕业设计（论文）指导工作，在疫情期间将毕业设计（论文）进展所受影响尽力减到最小，确保毕业设计（论文）质量线上线下实质等效。毕业设计中期检查工作中，同学们精心准备，认真答辩，积极展示毕业设计取得的阶段性成果，就让我们一睹为快吧，就让我们一睹为快吧：

员工姓名：王亚昆

班       级：工业2016-01班

指导教师：郭   鹏

毕设题目：考虑工作模式选择的并行机调度优化策略研究

一、概况

并行机调度(Parallel Machine Scheduling, PMS)问题是现实生活中厂矿企业经常面临的一类问题,调度的目的是将工件分配给各机床,并对各机床上的工件进行排序使完成所有生产任务的时间最小化。近年来研究此类问题的文献层出不穷，考虑到实际生产环境中常常有一些预处理操作或是等待导致工件的实际加工时间大于其原本的加工时间。所以本文在经典并行机调度问题的基础上考虑工件带有阶梯恶化的性质且赋予其不同的加工策略，例如在钢铁企业生产中可以赋予某铁水一定的保温措施延长其可被加工的时间窗口，防止其在等待加工期间温度降低导致无法加工。基于现今各行业提倡的绿色生产的思想，本文所提出的模型期望在能源消耗低的前提下实现最小化最大完工时间的目标。在求解方法上，本文主要采取一种基于分解的思想，将这一较为复杂的问题分解为工件模式选择，机器分配与排序三个部分，采用列生产的方法求解，期望为此类复杂的调度问题求解提供一种新思路。

二、任务分解

毕设分为以下几个任务：

1.首先通过查阅文献，学习了解并行机调度问题，归纳当前并行机调度问题研究概况。

2.建立考虑工作模式选择的并行机调度混合整数规划模型，并对模型进行优化。

3.利用Dantzig-Wolfe分解法对模型进行分解，并设计列生成算法进行求解。

4.进行大规模算例实验。

三、已完成工作

1.考虑工作模式选择的并行机调度混合整数规划模型建立。

经过大量文献阅读及实际的测试，优化后的模型采用网络流变量进行建模。问题可被描述为1.j个工件，m台同质机器。2.每个工件必须被安排至一台机器上进行加工。3.每个工件只有一个前序工件，一个后序工件。4.能量约束。5.时间约束。6.最小化总能量消耗和总拖期时间的加权和。模型的符号描述如下表：

 模型符号描述

利用Java+Cplex编写程序对模型进行求解，验证了模型的正确性。

2.Dantzig-Wolfe分解法对模型进行分解，并设计列生成算法进行求解。

利用Dantzig-Wolfe分解法对上述模型进行了分解，建立了集划分模型。

完成模型分解后设计列生成算法对模型进行求解，本文设计的列生成算法框架示意图如下：

列生成算法框架图

以六个工件，二台机器的算例为例展示列生成算法求解结果，算例数据如下图所示：

求解后生产计划甘特图如图：

四、 下一步工作计划

1.对列生成算法中的子问题求解进行优化，考虑采取动态规划的思想开发算法，提高子问题求解效率。

2.对初始列生成进行优化，考虑用启发式方法生成初始列。

3.算法优化完成后进行大规模算例实验。

4.完成毕业论文撰写，准备毕业论文答辩。

问题一：并行机调度问题研究在实际生产中有什么意义？

回答：在企业的实际生产过程中往往存在短期内收到大量不同订单的需求，而只有有限台加工机器的情况，并行机调度研究就是运用运筹学的方法合理安排这些订单加工与机器的对应关系，并对订单加工顺序进行排序，使得企业尽量在交付期限内处理完这些订单，获得最大的效益。

问题二：研究的成果能否落地加强实际应用？

回答：本文研究的考虑工作模式选择的并行机调度问题针对的是工件加工有时间窗口要求的特殊问题，此类问题对应于实际生活中的钢铁生产企业等，优化模型最终求解得出的结果可以为钢铁生产企业提供一种即节约能源又尽快完成订单生产的调度方案。此外，利用列生产算法对该问题进行求解，也是探究了精确算法在大规模实际调度问题中的求解效果，相比于元启发式算法可以得到质量更优的解，本文可以为这一类大规模复杂调度问题求解提供一种新思路。

毕业设计是对本科阶段基础理论与专业知识的一次综合应用。在学科竞赛与专业教育的熏陶下，我的独立学习和科研能力有了极大的提升。在毕业设计选题时，我决定挑战一下自己，选择难度较大的调度优化建模与精确求解方面的题目。

在进行毕业设计任务拆解时，我对如此复杂的问题顺利完成感到颇有压力。在毕业设计初期，郭鹏老师每次都鼓励我，给予了我莫大的信心与支持，同时还提供了大量的参考文献和示例代码。在多次的在线指导过程中，郭老师引导着我阅读文献与学习算法理论。在对并行机调度问题有了一定的认识与理解后，我经过多次尝试终于建立出模型并验证成功。在建模取得进展的那一刻，我感到无比的兴奋。在设计算法方面，我又恶补了许多运筹学的基础知识，撰写代码，不断地编译调试，在多次试错后终于完成了对原始模型的分解。虽然因疫情影响我与郭老师并不能见面，但是他在毕设过程中对我的学习和个人生活都提供了耐心指导和悉心关怀。郭老师对于我的各种问题都及时在微信上回复，并且细致地进行讲解。在我遇到困难与挫折时与我长谈一两个小时，为我的毕设能顺利进行提供了很多帮助。另一方面，郭老师也十分关心我的未来科研发展和职业规划，经常为我提供出国留学选择学校方面的指导，点亮了我之后的学术发展的道路。感恩郭老师孜孜不倦的辛勤教导。