初始工件带有释放时间的返工工件重调度的分段插入算法

摘要

初始工件带有释放时间的返工工件重调度的分段插入算法，根据初始调度有机器空闲的特点，有效的利用了机器空闲时间和初始工件可延迟的最大时间。根据返工工件和生产一个新工件相比通常具有初始时间较短的特点，将返工工件按照SPT(越短处理时间越早加工)的规则，尽可能多的插入初始调度，无法插入的返工工件则追加到最后按照SPT规则依次调度。该算法保证了决策的有效性，在保持了原生产系统稳定的前提下，极大的提高了生产效率。本发明针对RRJS生产问题提供了切实可行的重调度算法，该算法的提出对于RRJS生产问题中返工工件的重调度有一定的参考价值，对提高我国这类生产系统领域中的返工重调度算法具有重要的指导意义。

说明书

技术领域

本发明涉及工业工程领域中离散制造系统的返工工件的加工管理技术，是一种修正式的重调度方法。具体地，针对例如半导体、石英玻璃等一种生产中已知初始工件带有释放时间,优化目标任意的初始调度,重调度的目标是在满足初始工件具有最长等待时间约束下,最小化所有工件的最长等待时间问题(rescheduling rework jobs on a single-machine), 简称为RRJS的方法，即提出了一种分段插入启发式（Segment Insert Heuristic）算法，简称为SIH算法：这种算法在满足约束的前提下以充分利用设备的空闲时间，将返工工件更多的插入初始调度为思想，以提升重调度决策的有效性、生产线的高效性和制造系统的稳定性。

背景技术

调度问题一直以来是理论研究和生产实践的热点，工件排序也是比较经典和复杂的问题。在生产实践中，通常在生产前计划好工件的调度顺序，称为初始调度。所谓重调度就是指在已经制定好的初始调度执行前，由于实际出现例如：新工作到来、机器故障、人员变更、紧急工作到来、返工工作、原材料不能按时到达等各种复杂情况，初始的调度不能适应实际状况，在条件允许的情况下对初始调度进行调整，从而获得当前的最优调度。

重调度问题已经引起国内外研究者和实践者的重视。包括：处理新任务的到来的重调度,预加工工件不可用的重调度,机器中断的重调度，针对具体实际问题的重调度,多目标的加工车间重调度,流水车间环境下的重调度,任务随时间恶化的重调度等；问题方法包括：动态规划、鲁棒优化、分支定界、启发式算法、智能算法等等。

在Operation Research（运筹学）期刊上发表的Rescheduling for New Orders（新到工件的重调度）一文在工件重调度领域的方法比较有代表性,他们研究了几种单机重调度问题, 提出了几种最优算法。但是所提出的方法仅适用于解决约束为：初始工件的最大延迟数、延迟数和、最长延迟时间、延迟时间和受限于某一定值,目标函数为最小化完工时间和最小化最大完工时间工件重调度的问题。之后的很多研究者和实践者沿着这个思路进行了重调度的研究。但是现有技术方法没有考虑到以下情况：（1）初始工件带有不同的到达时间，初始调度存在机器空闲时间。（2）重调度目标和初始调度目标不同。（3）初始工件受到等待时间的约束。

在实际生产中即使初始调度针对某一目标函数是最优的调度,由于需要对返工工件进行处理,从而打扰了初始调度,根据实际需要可能要调整目标函数,因此初始调度对于重调度的目标来讲就不一定是最优的调度了。另外,初始工件到达通常具有不同时间,因此初始调度大多带有机器空闲时间。同时,在离散制造业中,很多工位上根据工件制造工艺的要求,在工件到达后必须在一个时间窗口内进行操作加工,即受到等待时间的约束。在各种约束条件下，RRJS问题属于典型的组合优化问题，RRJS问题为多项式时间不可解（即NP难）问题，即如何确定最佳的重调度方案是一项困难的工作。因此针对上述普遍存在的实际问题亟待发明一套行之有效的解决方法。

发明内容

本发明针对已知一任意优化目标                                                的初始调度，包含一组数量为  的初始工件 ,每个工件具有不同的释放时间为 ,，当最初的工件已经调度完毕，但未开始处理之前有一组数量为  的需返工工件 到来，需要返工的工件到达时间、装设均为0；不失一般性，如果已经有一部分工件已经处理，则把剩余未处理的工件看成是最初的工件。在满足初始工件最长等待时间限值为 的条件下,根据返工工件情况进行重新调度,从而获得目标为所有工件最小化最大等待时间的重调度 问题。

本发明涉及的初始工件带有释放时间的返工工件重调度的分段插入算法，具体步骤如下：

第1步：将返工工件按照处理时间的非降序排列，得到调度 ，表示第 个位置的工件号，计算第 个位置之前的处理时间和，；

第2步：按下列步骤执行：

第2.1步：如果 ,并且 ，执行第2.1.1步；如果 ,,则 ；如果 ；

第2.1.1步：如果且,则计算，；选择，执行第2.2步，否则 ；如果执行第2.1步，如果 则 执行第2.2步；

第2.2步：如果，在之前插入，否则 ；更新中工件的所有开始时间,使 的开始时间等于 ,；如果 ；否则； ,=，，返回到第2.1步；

第1步和第2步中上角标表示工件类型，即  表示初始工件,  表示返工工件，小括号内符号表示调度类型，即  表示初始调度， 表示重调度， 表示重调度中返工工件的最大等待时间；  和分别表示工件的完工时间与开始时间， 表示初始工件可以延迟的最大时间，  表示机器空闲时间和； 表示子调 紧接着子调度 后执行的调度； 表示在前一段插入返工工件之后紧挨着当前段之前的剩余空闲。 

 SIH算法时间复杂度为：，计算速度较快。对于SIH算法主要从三方面进行设计：

（1）如何找到插入返工工件的位置；

（2）如何有效的利用机器空闲时间和初始工件可延迟的时间；

（3）安排哪些返工工件插入。

针对第（1）方面：给出“分段点”的定义：初始调度中空闲时间结束的时刻称为“分段点”。“段”的定义：从block中允许往后推迟的一组连续调度的初始工件中第一个初始工件开始的时间,到紧接着block的空闲时间结束的时刻,称为“段”。在每段之前为插入返工工件的位置。

针对第（2）方面：计算出每段中含有的初始工件可以往后延迟的最大时间，即取每段中每个初始工件允许延后时间的最小值和每段中包含空闲时间的最大值。

针对第（3）方面：将已经按照排好顺序的返工工件，在满足小于等于各段延迟的最大时间的条件下，依次尽可能多的插入到各段之前。

值得注意的是：如果当前段插入完返工工件之后，仍有空余时间但不足以插入任何一个剩余的返工工件，则将该空闲时间移到下一段之前，和下一段可延迟的最大时间整合起来，进行下一段的返工工件插入。

本算法的优点在于，SIH算法根据初始调度有机器空闲的特点，有效的利用了机器空闲时间和初始工件可延迟的最大时间。根据返工工件和生产一个新工件相比通常具有初始时间较短的特点，将返工工件按照SPT(越短处理时间越早加工)的规则，尽可能多的插入初始调度，无法插入的返工工件则追加到最后按照SPT规则依次调度。该算法保证了决策的有效性，在保持了原生产系统稳定的前提下，极大的提高了生产效率。

总之本发明针对RRJS生产问题提供了切实可行的重调度算法，该算法的提出对于RRJS生产问题中返工工件的重调度有一定的参考价值，对提高我国这类生产系统领域中的返工重调度算法具有重要的指导意义。

附图说明

图1是本发明SHI算法中所有情况的甘特图。

具体实施方式

本发明提供的返工工件重调度方法的实施方式如下：

本发明提供的重调度方法在具体实施阶段需要满足的条件为：企业必须有支撑生产的制造执行管理系统(MES)，或者与实际生产同步的数据库。

重调度系统应包括三块内容：企业数据库、本地数据库、重调度软件系统。大致流程为，软件系统从企业数据库中读取数据，存入本地数据库，一旦发现有需要返工的工件，则启动重调度软件系统，然后将重调度后的数据通过软件系统写回至企业数据库，以供MES系统使用，使线上的工作人员能及时依照最新的排程方案进行加工。以下就各部分详细阐述本发明的实施方式。

由于企业数据库的结构往往是异构的，且同一企业内，由于生产线的不同，所对应的数据库也会不同。然而，本发明提供的SHI算法对生产线并无特殊需求，属于适用性较广的算法。所以，要使SHI算法能够适用于所有的生产线，需要先转换企业数据库至本地数据库。SHI算法对数据的需求并不复杂，只需要有初始的调度方案信息即可。

本地数据库的作用在于存储从企业数据库中加载的数据，目的在于比较最新的数据与前一次加载数据的区别，以判断是否启用重调度系统。一旦有需要返工的工件信息便需要重调度。本地数据库的另一作用在于存储每次重调度前后的排程方案，以方便企业通过历史数据分析重调度的有效性。

重调度软件系统，该部分作为重调度系统的核心部分作用在于控制企业数据库与本地数据库，并实现SHI算法。在企业数据库方面，软件负责加载企业数据库中需要的数据，并存入本地数据库，目的在于及时发现启动重调度条件。由于企业数据库的数据量一般较大，可以采用增量形式对数据进行刷新。

另一方面，SHI算法实现是软件系统的主要部分，一下详细阐述SHI算法的实现过程。

如图1中，(a)到(f)说明了SIH方法如何计算每段中初始工件允许延迟的时间,以及如何插入返工工件的所有情况。 | 表示分段点的位置, * 表示当前段初始工件可以往后延迟的最大时间，灰色部分表示为当前操作的段，加粗边框表示已经确定的工件顺序。具体如下：

(a)中说明找到第一个分段点和第一段,在这段中包含 两个初始工件,首先计算它们允许延迟的最大时间为，即  所示，然后尽可能多的依次选择未调度的返工工件插入  之前进行调度。

(b)中我们已将插入的返工工件确定,找到第二个分段点和第二段，因为 和  仍然可以推迟，所以第二段中包含从  到 共六个工件，计算它们允许延迟的最大时间为 ，即 所示，然后尽可能多的依次选择未调度的返工工件插入 之前进行调度。

(c)中  和 不能再推迟或者可以延迟的时间不足以调度任何一个未调度的返工工件,因此它们被确定。找到第三个分段点和上一个相同,而第三段中包含 四个工件,计算它们允许延迟的最大时间为 ，即 所示。

(d)中  之前的工件不能再推迟或者可以延迟的时间不足以调度任何一个未调度的返工工件，因此被确定。找到第四个分段点和包含 的第四段，计算允许延迟的最大时间为 ,即 所示，然后尽可能多的依次选择未调度的返工工件插入 之前进行调度。但未调度的返工工件中最小的处理时间均大于之后,所以没有返工工件被调度。

(e)中即使最大限度推迟 和 之前仍不能插入任何一个未调度的返工工件，因此确定 和 在原来的位置进行调度。找到第五个分段点和仅包含 的第五段，计算允许延迟的最大时间 ，即 所示, 然后尽可能多的依次选择未调度的返工工件插入之前进行调度。

以此类推,如果所有返工工件均被调度,则结束,未被确定的初始工件保持初始调度方案不变。(f)中如果所有初始工件均被确定,仍有未调度的返工工件,则按照SPT规则追加到最后一个初始工件之后进行调度。

最后，说明本发明SHI算法的性能表现。

（1）应用SIH算法能够得到RRJS问题中没有一个返工工件在最后一个初始工件前调度的最优调度 。

（2）应用SIH算法能够得到RRJS问题中所有返工工件都在第一个初始工件前的最优调度。

（3）应用SIH算法能够得到RRJS问题中非（1）和（2）的情况,且最后一个返工工件之前没有机器空闲的最优调度。

（4）应用SIH算法能在最坏的情况下得到一般RRJS问题的解 , 表示RRJS问题的最优解。