基于最高响应比法和匈牙利算法的调度系统在流水线、仓储系统中的应用研究

说到最高响应比法, 在业界人们并不陌生, 它是一种既考虑作业执行时间也考虑作业等待时间的算法;而匈牙利算法则是由匈牙利数学家Edmonds提出的部图匹配最常见的算法。虽然, 这两种算法在实践中, 已经被广泛运用, 但将其通过调度系统应用于流水线系统和仓储系统中却不多见, 为此, 本文将以此为线索, 来探索其在流水线系统和仓储系统中所构建的模型及其应用价值。在生产实践中, 流水线系统和仓储系统往往都是单独运行的系统, 两者间缺乏有效的互通与衔接, 因而时常造成大量的时间与成本浪费以及资源闲置的状况。为此, 本文将针对上述问题, 提出了以最高响应比法和匈牙利算法为基础的, 通过调度系统完成流水线系统和仓储系统统一调配的, 提升两系统间合理配合度的应用研究。

为了便于分析, 我们首先要阐述的是, 调度系统与流水线系统、仓储系统之间的关系, 即当调度系统接到某一生产任务时, 通过最高响应比法, 并根据各流水线系统的工作状态, 计算得出最优解, 最终将生产任务单下发给最优的流水线系统;

当该流水线系统即将开始生产时, 由流水线系统发起需料申请, 调度系统接收到申请后, 通过匈牙利算法, 计算出最优的仓储系统, 并将物料出库, 最终将该物料送给流水线系统;

当该流水线系统完成生产任务时, 再由流水线系统发起送料申请, 调度系统接收到申请后, 通过匈牙利算法, 计算出最优的仓储系统, 将物料入库 (其关系图见图1) [1]。

由图1可以看出, 调度系统是针对任务级的调度, 整个调度系统既不干扰流水线系统内部工序的安排, 也不设计仓储系统中每次取货的路径。这样设计的目的在于, 尽最大可能性地不要干涉流水线系统和仓储系统这两个独立系统的自身工作流程, 又能够通过任务的合理调配, 达到效率的最大化[2]。

最高响应比优先算法 (HRN) 是对先来先服务 (FCFS) 方式和短作业优先 (SJF) 方式的一种综合平衡。所谓先来先服务方式, 就是只考虑每个生产任务的等待时间而不考虑执行时间的长短;所谓短作业优先方式, 就是只考虑执行时间而不考虑等待时间的长短, 因此, 最高响应比优先算法的调度策略就是综合考虑每个生产任务的等待时间长短和估计需要的执行时间长短, 从中选出响应比最高的生产任务投入执行。

计算最高响应比R的公式为:R= (W+T) /T。其中T为该生产任务估计需要的执行时间, W为生产任务在堆栈中的等待时间。每当要进行生产任务调度时, 调度系统通过计算每个生产任务的响应比, 选择其中R最大者投入执行。

鉴于此, 本文所建立的模型假设有四个独立的流水线系统, 当每个流水线系统做相同的任务时, 所需时间都是一样的。只要生产任务在该流水线系统中开始执行, 就不能再中止该任务的运行 (原因是中止任务将导致物料的损坏和极大的时间成本损失) 。另外, 本文所建立的模型假设其生产任务初始化都是没有优先级的, 即所有任务都是平等的, 除非确实需要提升某个生产任务的优先级的情况下, 才允许进行优先级的调整。

所谓匈牙利算法是一种用增广路径求二分图最大匹配的算法。该算法的核心即要让系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。

匈牙利算法的前提是, 假设第i个工人做第j件事的时间是Cij, 其决策变量是Xij, 其公式如下:

通过匈牙利算法建立的数学模型为:

在这里, 本文所建立的模型假设是有两个独立的仓储系统, 由于, 两个仓储系统的地位是平等的, 即各个物料既能在仓储系统1中找到, 又能在仓储系统2中找到。故此, 本文所建立的模型即需要制定一个任务分配方案, 使得出入库所需总时间最短, 工作效率最高[3]。

为方便计算, 我们给出如下假设:即当调度系统先后接到四个相同优先级别的生产任务, 每个任务需要进行的时间 (即任务进行时间) 分别是67、39、45、72分钟, 而每个流水线系统距离空闲状态的时间 (即任务等待时间) 分别为32、17、27、13分钟。

通过计算我们可以看到, 所有任务的最高响应比R, 如表1所示:

通过观察表1我们可以发现, 流水线系统4在做任务4时, 最高响应比R最高, 因此, 将任务4分配给流水线系统4, 并重新生成任务等待时间和最高响应比R, 其结果如表2所示:

通过观察表2我们又发现, 将任务1分配给流水线系统2, 并重新生成任务等待时间和最高响应比R, 如表3所示:

通过观察表3我们发现, 将任务3分配给流水线系统3, 并重新生成任务等待时间和最高响应比R, 如表4所示:

综上所述:在任务优先级相同的情况下, 流水线系统1~4分别需要71、84、72、85分钟即可完成这四个任务, 并且完成所有任务最多需要85分钟。

如果我们假设在这4个任务中, 有优先级差别, 且任务2优先级最高, 则重新计算最高响应比R, 则可得出表5的结果:

通过观察表5我们可以发现, 将任务2分配给流水线系统4, 并重新生成任务等待时间和最高响应比R, 详见表6:

通过观察表6我们又发现, 将任务4分配给流水线系统2, 并重新生成任务等待时间和最高响应比R, 见表7:

通过观察表7可以发现, 将任务1分配给流水线系统3, 并重新生成任务等待时间和最高响应比R, 详见表8:

综上所述:在任务优先级不同的情况下, 流水线系统1~4分别需要77、89、94、52分钟即可完成这四个任务, 并且完成所有任务最多需要94分钟。

为方便计算, 我们将该仓储系统和需要分配的任务分成如下三种情况进行计算:

1) 假设有两个仓储系统, 且此时正好同时有两个出入库任务需要分配, 即i=j (仓储系统数等于任务数) [4], 每个仓储系统执行每个任务的时间如表9所示:

由此我们可以得到表9的时间矩阵为:各行各列减去最小元素后得, 最终得出最优解为, 即最小总时间z为6分钟。

2) 假设有两个仓储系统, 且此时只有一个出入库任务需要分配, 即i>j (仓储系统数大于任务数) , 且每个仓储系统执行每个任务的时间如表10:

由此我们可以看到, 由于仓储系统数大于任务数 (时间效益矩阵非方阵) , 故需要利用加边法 (添加行或列) 使其变为方阵, 元素用0, 即一般采用的“加边补零法”[5]。处理过的表10的时间矩阵为:各行各列减去最小元素后得, 最终得出最优解为, 即最小总时间z为3分钟。

3) 假设有两个仓储系统, 且此时同时有三个出入库任务需要分配, 即i<j (仓储系统数小于任务数) , 每个仓储系统执行每个任务的时间如表11所示:

由于仓储系统数大于任务数 (时间效益矩阵非方阵) , 故需要利用加边法 (添加行或列) 使其变为方阵, 元素用该列 (或行) 的最小值, 即一般采用的“加边补最小值法”[5]。处理过的表11的时间矩阵为:各行各列减去最小元素后得, 最终得出最优解为, 即最小总时间z为10分钟。

通过上述的假设与运算, 我们可以看到, 把基于最高响应比优先算法和匈牙利算法的调度系统应用到流水线与仓储系统中, 可以大大优化整个系统的工作效率。比如在流水线系统中, 如上文假设的四个任务的优先级完全相同的例子, 完成所有任务最多需要104分钟, 而调度系统通过使用最高响应比优先算法后, 将所有任务完成时间降低至85分钟, 工作效率提高18%;同样, 在仓储系统中, 如上文假设的仓储系统数等于任务数的例子, 完成所有任务最多需要9分钟, 而调度系统通过使用匈牙利算法后, 将所有任务完成时间降低至6分钟, 工作效率提高33%。所以, 通过对调度系统的使用;通过对算法的提升。通过对数学模型的计算, 本文所探讨的方法能够较好地解决系统间任务分配问题, 而在工作实践与验证中, 我们也看到了, 将孤立的流水线系统和仓储系统有机的联系起来, 不仅能形成一个完美的整体, 同时, 还将大大提高工作效率, 其所获得的结论也验证了我们的假设。