车间生产调度及优化方法研究_王怡航.pdf

内燃机与配件 技术创新与应用车间生产调度及优化方法研究王怡航（武汉工程科技学院，湖北 武汉 ）摘要：随着用户对产品需求的快速变化，现代制造企业需要进行多品种、小批量生产。这种生产方式使生产的计划、组织和控制变得更加复杂。因此，生产调度问题作为生产管理系统的核心内容和关键问题，其研究具有重要的理论和实用价值。本文主要针对作业车间的调度问题进行了理论分析与案例讲解，案例讲解主要包括几种启发式算法与遗传算法；两者进行对比，得出启发式算法改进初始解的生成。关键词：生产调度；启发式算法；遗传算法中图分类号：文献标识码：文章编号：（）（，）：，：；作者简介：王怡航（），男，河南省禹州市，汉族，学生，计算机网络技术研究方向。调度问题的优化方法调度问题相关的优化方法是从问题的全方面考虑的，通过准确的或者大致的求得解析模型的最好的解或者次优的解。在全方面的考虑下，带着操作任务在可控的时间内去开展搜索的相关工作，通过此方法可以得到比较好的解。优化问题的本质其实是数学问题，是基础的数学规划问题，但是我们用此方法只能解决小部分的优化问题，对于那些比较复杂的生产方面的调度问题，单纯的用优化方法不太容易保证全局最优。在这些复杂的生产方面的调度问题上，我们可以结合相关的启发式算法，利用他们的互补性，以达到更好的效果。案例分析与研究 基于优先级规则求解单机调度问题优先级规则包括择优选定加工时间最短的工序的 法 则，择 优 选 定 最 早 进 入 可 排 工 序 集 合 的 工 件 的 法则，择优选定完工时间比较紧的工件的 法则，择优选定剩下加工时间最长工件的 法则，择优选定剩下加工时间最短的工件的 法则，择优选定余下工序数最多的工件的 法则，随机排序的 法则，松弛时间是指在不影响交货的前提下，任务的机动时间的 法则，优先选择关键比最小的任务。关键比为任务允许停留时间和任务剩余工序加工时间之比的 法则。假设：在生产线上，有个作业需要在单个工作台上完成车间作业排序的问题，在工期开始之前，有五名客人提交了生产订单。订单的原始数据如表所示：表订单原始数据订单（按时间先后）加工期天完工期天 使用不同的优先级规则方法计算得到的总完成时间，平均比较时间和平均延期情况如表中数据所示，可以发现，使用 方法比其他的方法要略优，但是这不具备普遍性，这也是优先规则存在的局限性。表不同规则比较规则总的完成时间平均完成时间平均延期 （先到优先）（最短作业时间优先）（交货期优先）（后到优先）随机 （剩余松弛时间最短）基于 算法求解 问题 算法计算步骤如下：、从加工时间矩阵中找出最短的加工时间。、若最短的加工时间出现在上，则对应的工件尽可能往前排；若最短加工时间出现在上，则对应工件尽可能往后排。、若所有工件都已排序，停止；否则，转步骤（）。DOI:10.19475/ki.issn1674-957x.2023.01.019 年第期对于如下加工时间矩阵，利用 算法计算作业排序如下。表加工时间矩阵 （，）基于一般启发式算法求解 问题对于一般的流水车间的排序问题，使用分支界定法能够得到 问题的最优解，但这种方法很难应用于实际的生产当中，由于实际的工件数量大，导致计算成本非常高，因此分支界定法的经济性不高。为了解决实际生产中的排序问题，科研工作者创造了很多种启发式算法。该类方法计算量小，计算结果好，因为被广泛运用。下面介绍几种常用的启发式算法。帕尔姆法帕尔姆法于 年由 提出，该方法根据工件的斜度指标来进行排序，能够得到一个比较接近最优解的方案。该方法计算公式如下：（）（）机器数，工件在机器上的加工时间。帕尔姆方法安排作业顺序的规则是：按照各个工件计算得到的斜度指标非递增的顺序排列工件。以如下问题为例，对于 排序问题（即个工件台设备，流水作业排序问题，目标是使最长流程时间最短），各个工件在每台设备上的加工时间如表的加工时间矩阵表所示。表加工时间矩阵 （）（）用帕尔姆法得到的最优排序为：（，）或（，）/关键工件法关键工件法计算步骤如下：（）计算每个工件的总加工时间；（）剩下的工件，规定为工序的总数，若，则按递增的顺序排成一个序列，若，则按 递减的顺序排列成一个序列；（）顺序（，）即为所求顺序（近优解）。表工件在每台设备上的单件工时与总工时工件 以如下工件为例，有个工件，在台设备上加工，每个工件分别在不同的设备上加工耗时情况如下表所示。（，；，）根据上述计算结果可知，号工件的加工时间最长，为。因此将第三号工件设为关键工件，剩余的，号工件根据上述第二步计算，可以得到，号工件为，号工件为，因此根据第三步可以得出近似最优解的排序为（工件，）。表工件在每台设备上的单件工时与总工时 法 法是 算法的扩展方法，被认为是好的具有鲁棒性的启发式算法。算法步骤如下：将台机器分组，产生个两台机器问题的集合，然后利用 算法获得 个加工顺序（每个两台机器问题获得一个加工顺序）；选取这 个加工顺序中考核指标最好（一般为 最短）的加工顺序作为近似最优调度解。法是 算法的扩展方法，从个排序中找出近优解。表加工时间矩阵 当时，；当 时，；因此，根据上述计算方法得到的最优顺序为（，）。基于遗传算法求解作业车间排序问题遗传算法是一种基于自然群体遗传演化机制的高效探索算法，由美国学者 于 年首先提出来的，通过模拟达尔文的遗传选择和自然淘汰的生物进化过程来求解。遗传算法将实验的对象看做是一个个不同的染色体，算法的主体思想是仿照染色体变异的方法，将不同个体之间进行交叉和变异，从而达到产生新个体的目的。运用特定的评价函数，对变异后的种群中的个体进行筛选，依据优胜略汰的原则，不断优化群体，并且使用搜索算法获取种群内的最优解。遗传算法步骤图遗传算法的基本流程遗传算法的主要步骤如下：、对种群中的每个个体进行编码，编码的目的主要是便于运算；内燃机与配件 、构造适应度函数。、当适应度函数确定以后，对种群进行筛选，选中的个体组成新种群，形成一个可以繁殖下一代的群体；、进行交叉操作，产生新解；、进行变异操作，并重复的步骤，直到满足一定的条件指标。遗传算法与启发式规则比较例：有一个 排序问题（即个工件台设备，流水作业排序问题，目标是使最长流程时间最短），各个工件在每台设备上的加工时间如表 的加工时间矩阵表所示。表加工时间矩阵 （）启发式算法（选用帕尔姆法）：（）（）最优排序为（，），按（，）计算结果为 （）遗传算法核心代码如下：；设置种群包含的个体数目；设置最大遗传代数；设置代沟；设 置 交 叉 操 作 的 概 率；设置变异操作的概率；，；，；，；，；，；，；输入加工机器集合矩阵；，；，；，；，；，；，；（，）；（最长流程时间为：），（）运行结果如下：图工件加工甘特图图迭代图（）改进遗传算法核心代码如下：；设置种群包含的个体数目；设置最大遗传代数；设置代沟；设 置 交 叉 操 作 的 概 率；设置变异操作的概率图工件加工甘特图图迭代图经上述运行结果可知，用启发式算法算出的结果为，遗传算法算出的结果趋于，启发式算法与遗传算法结合算出的结果趋于。很明显在流水作业排序问题中遗传算法得到的结果比启发式算法结果好，启发式算法与遗传算法结合得到的结果相比单独使用两种方法更好。总结本文主要研究了车间调度中的一些问题，通过实验数据对比，优先级规则在实际单机排序应用过程中存在一定的局限性，算法只适用于两台机器的调度问题，一般启发式算法计算方法比较复杂，而本文通过启发式算法与遗传算法结合得到的结果在实际调度问题中趋于更优。参考文献：陈荣秋生产与运作管理（第二版）科学出版社 张建林 定量决策五大类问题 个运作管理经典案例分析 电子工业出版社 闫盖 基于遗传算法的车间调度算法 南京：南京林业大学