洗发水行业中带有有限缓冲存储的流水作业调度论文翻译.docx

洗发水行业中带有有限缓冲存储的流水作业调度论文翻译洗发水行业中带有有限缓冲存储的流水作业调度1. 介绍 在本文中，我们解决了发生在精细作业行业中的调度问题。整个生产系统由三个方面的服务系统组成：生产，临时存储以及包装系统。生产过程是由包装过程主导的，其生产目标根据已知的具有决策力的市场需求而确定的。包装是在有足够的生产存储能力的假设下完成的。生产系统负责生产那些随后将在包装系统入瓶的产品。存储系统是产品生产与包装的接口环节，当一个产品生产出来时先被传输到存储区在到达包装系统之前。包含很多包装生产线的包装系统每天都要根据中期生产计划确定每一个包装线接下来24小时的产量。包装线的中期规划问题是针对诸如Mocquillon等的批量问题。一旦产量确定了，它就将产品的计划生产顺序发送给生产系统，同时也发送给各个包装线。几个生产单元组成生产系统，该系统负责生产产品并将产品批量输送给存储系统。带有存储箱的一批货物是根据计划为准备工作的包装线提供货物的。一个批处理是一个固定的不可分割的相同的洗发产品的处理量（12吨）。这里，不可分割指的是同一批次的产品只能存放在一个存储箱里并且只能在一个包装线完成装瓶工作。存储设备包含了很多不同存储能力的存储箱，并且每一个存储箱是直接连接到包装线的一个子系统上的。这就意味着一个批次的产品只能由之后要对它进行包装处理的包装线决定的存储箱存储。图一举了一个简单的例子，该例子包括3个生产单元，5个不同容量的存储箱，4条包装线。本文中我们主要讨论由不同存储容量引起的调度问题。这里有几家不同的洗发水公司，每家的化学配方和外部包装特征都不同。因此，就算存储箱没装满，也不能将不同家的洗发水装进这个存储箱里。因此，下一个即将被存储的批次如果跟之前存储的洗发水不是同一家的，则一定要在新批次到达之前将存储箱刷干净。在这个临时存储调度问题中，我们的目标是使存储箱清洗次数最少同时使产品批次的延期的最小。延期是在交货期的基础上限定的，而交货期是对应于包装线该批次洗发水包装完毕的时间。在很多生产过程中中间存储还是至关重要的，像本文中的处理过程，在化工业中的应用更为广泛。从文学的高度粗略看一下，在解决车间调度问题的时候，有限中间存储设备的使用越来越广泛。在调度问题中提到了三种不同的中间存储方式。第一种是无限制的中间存储（UIS）：这里假设有一个无限的存储空间可以在任何时候容纳下所有的工作量。第二种是没有任何中间存储(NIS)：该方式假设经典的批次之间没有等待时间并且组织对生产资源的约束。最后一个是有限的中间存储(FIS)：这里假设只有有限的中间存储空间，只能装进有限数量的产品。有限中间存储可以被分为如图二所示的四种类型。FIS的第一种类型，如图中所示，是基于存储资源和车间机器之间的交互的，这就导致了共享FIS和专用FIS的一个区别。这种分解可以提炼分离平行的单位和单一的资源。如果存储资源在工作安排中至多被两台机器同时使用的话则可以说该存储资源是专用资源。两种专用存储模型就出现了：（1）单机专用存储模型：它和调度学中广泛提到的经典中间存储缓冲区相对应。这种模型适用于可以混合存放多种产品的车间。（2）并行专用存储模型：在这里，调度作业上的存储单元可能是必要的，如果被认为是非零的安装成本。这种模式是非常适合不同液体类产品不能一起存储的化工行业。该模型被诺曼（1999年），Ku波段和卡里米（1988），Kim等人（1996年）多次在文献中提到和考虑。如果车间中至少3台机器在共享某资源，则该存储资源就可以说是共享存储。对于这种情况我们也考虑到了两个模型：（3）单机存储共享资源：机器是要通过竞争来共享这些资源的。这种模型被广泛应用在网络系统中，还被科斯拉在1995年在印刷电路板的制造业中提到。（4）并行单元资源共享：几个有着不同容量的存储单元组成的一个多元化车间。这似乎说明该工作中提到的存储能力和这个模型是一致的。其他的一些包括存储平台的调度问题在很多文献中也有提到。显然，像专用单元这样的简单模型已经被当成了很多研究的主题。但是想并行共享单元这样的模型却更加重要和复杂。它们可以作为多级车间的复杂阶段甚至瓶颈阶段的代表。当输送时间和启动时间非零的时候，存储的重要性可与生产的重要性相比一番，因此它的调度值得更深一步的研究。竭尽我们目前的所知，还没有在并行共享单元调度方面的相关研究文献。本文中提到的存储箱以及有着特殊限制的并行共享存储将在第二部分详述。值得注意的是，这些约束使得3个调度问题的交叉点处成为有存储缓冲限制或者需要考虑安装时间及成本以及有固定间隔时间的调度问题。关于缓冲能力有限的调度问题，我们更感兴趣的是流水作业车间中的复杂问题。Papadimitriou和Kanellaki已经在1980年指明有生产时限的双机车间的决策问题为NP难问题。Gapta在1986年也指出与启动时间或成本相关的流水作业顺序问题是NP难问题，不管该车间有多少台机器，有什么标准或者是多少缓冲空间。但是本文中提到的一些特殊问题并没有对应的复杂结果。本文中提到的研究问题其实是一个复杂的现实问题，并且已经有了一定的理论结果，以辅助推导出一个有用的启发式算法。更为确切的说，这样我们就可以让大家知道，一些特定的问题是可以在一定时间内解决的，甚至可以找到一个精确的算法。然后该算法还可以被用来解决很多的一般性问题，甚至用来修复一些不可能解。我们还将这种启发式算法与有实际工程实施性的贪婪的启发式搜索和蚁群优化算法作了比较。值得注意到是，后者已经与模拟退火算法进行杂交以提高其解决问题的效率。不管怎样，很多的上机实验还是证明了专用的启发式算法的优越性。 其余部分安排如下：第2节进行问题陈述并展示初步的结果;第三节讲述解决算法，而第4节致力于这些算法的计算评价。最后，第5节给出了一些结论。2. 问题属性及陈述 21 问题的复杂性 考虑这样一个问题，n个批次的货物必须在L个储存箱间进行调度。箱子l的缓冲能力表示为bl(当箱子确定时，我们省略下标l)，它等价于箱子的容量。建模时当进行连续排空操作时，按存储箱的容量来进行处理比按照货物批次来处理更加灵活。我们有l个各种容量规格的存储箱和相应的每批次重量为12吨的货物。 每一个批次的货物由对一个存储箱的装载操作以及包括将一批货物从存储箱转移到包装线的排空操作所限制。一批12吨的同一家的洗发水产品:简单的说，每一批次的产品是一家，或者是规划范围内的相关联的几个批次的产品。每个操作需要一个固定的处理时间还有它自己的处理时间（这和包装处理是相关的）。. 每批货物还要有一个准备期，此处也就是和包装设备准备将洗发水装入瓶子的时间。交货期则是承诺的交货时间也即是完成时间。因此，理想来讲，批次k货物的操作应该从准备期开始，在交货期结束。如果操作在交货期之后完成的话，那么要求批次k停止操作的包装线需要等待其他批次的需求。单机的调度问题可以模拟作为一个特定的有限缓冲容量的双机流水作业问题：第一台机器处理负载操作，第二机处理排空操作，并且缓冲区则在要求这两个操作之间运行服务。 该调度问题的目的是为每一个批次的货物分配一个存储区并计算出每个负载操作的开始时间。同时，我们记Ck为完成时间，Lk为脱期，其中。根据工业问题，有额外的约束问题要回答，并在下面列出。抢时间是不允许的，在两个批次货物的开始时间是有一个最小脱期的。这个最小脱期是不确定的，我们规定。这个时间对应于需要往一个存储箱装入最小量货物的时刻，比包装线开始工作的时间靠前。有时，它也对应于使产品泡沫消失的时间在包装线重新处理该批次产品之前。在这种情况下，有：第二个最小的时间延迟，由DJ，K“，表示，必须尊重一个批次的排空操作的完成时间之间的j和批处理的装载操作的起始时间，j和k是计划连续在同一存储箱的持续时间这个时间延迟被定义如下：已知是一个固定的和已知的正整数。这个约束是包装设备强加上的，以确保如果包装线X时间延迟了，包装线y不会受到影响。清洁操作为蓝本的限制家庭依赖凹痕安装时间，这是预期。在这里，有限制意味着，的持续时间的设置时间只可以采取两个值。缓存批次i货物的存储箱k的有效期要在货物批次j的处理时间之后。这个有效时间的定义需要依赖以下两个因素：（1）它的容纳量（2）存储的最后一批货物的排空操作。具体定义如下：请注意，设置时间可能先于脱期，它们的顺序并不重要。图3描绘了一个单一箱子的调度问题，它是对于所介绍的限制的一个解释。它涉及到一个容量为20吨的存储箱及3个批次的货物。在这个例子中，批处理1和2的目的是相同包装线。他们属于同一个家庭，从而不需要进行设置，并因此，可以共享缓存区只要它的容量是足够的。第二批负荷运作在D1时刻开始，在第1批货物的排空操作后的两个单位时间内进行。D1，2的数值对应于需要有一个容量为12吨的存储箱的时间。批次2和3的目的是两个不同的包装生产线。它们也有不同的家，所以设置时间需要等到批次3的装载操作之后，从图三中可以看出，这个设置时间阻塞了机器以及缓冲区。批次3的完成时间在交货期之后，脱期为：。余下部分，我们将根据存储箱的容量来区分这些调度问题的类型。与将我们对装载操作的初试时间的定义局限在先前的一般定义不同的是，我们将为每罐容量的加载操作定义初试时间。这种不同的对装载操作的初试时间的计算称为结构特性。I，J，k是三批接连存储在罐l的货物，表1给出了批次k的装载操作的起始时间的结构特性的总结。我们要解决的是一个双目标调度问题，我们的目标是使得初试时间最小化，在这里相当于总安装时间最小化。定义的最长拖期是Lmax=max16k 。像往常一样在多目标理论中，我们寻找帕累托最优解的标准TST和Lmax：调度S是一个帕累托最优问题，当且仅当不存在另一个日程表，这样，TST（S0）6（TST）和Lmax（s0的）LMAX（6）至少有一个严格的不平等。这样的解决方案的比较是通过装置所谓的约束的方法进行的，我们将在后续的方式应用它：标准TST的约束下最小化LMAX 6，一个给定阈值的问题。众所周知，任何该约束问题的最佳方案是一个准为TST和Lmax的帕累托最优化问题。我们指是我们刚才定义的一个任意的双目标调度问题： L代表一个已知的存储箱的数量.我们现在转向之前介绍过的的复杂性的普遍问题，以及一些其特定的问题。陈述单向调度的NP难问题，从为之后的该问题的NP难属性做个铺垫。之后，我们会考虑实际情况下不允许有拖期的问题。我们将表明，它是在有限时间内，当箱子容量为12吨或者是20吨时是可以被解决的。而每个箱子容量都是24吨的复杂问题仍然是一个悬而未决的问题。让我们从问题开始：根据经典的3场符号的调度问题以及后来提出的多目决策的延展问题，这个个子问题可以记为引理2.1问题是一个NP难问题。证明：从问题开始入手，这是一个强NP难问题（Yuan等人，2006）。它与相关的 强NP难决策问题有着直接的联系，可能的Cmax值可能是伪随机数。最后一个问题是一个特殊情况下的NP难完全问题。这个决策问题和 问题也是有关联的，据此可以推断出后者是一个NP难问题。值得注意的是，是双机流水作业问题，它也说明后者是NP-难。引理2.1说明问题是一个NP难问题，这也说明一些更为普通的问题都为NP难问题。22 固定时间的子问题 现在，我们开始考虑不允许有拖期的子问题：更为精确的包装服务规定LMAX = 0。这里，所有的排空操作需在确定时刻开始，并在规定的完成时间完成。因此，我们必须有确定的分配安排，存储箱的货物批次要符合装载机器的开始时间，以达到总初试时间最小化的目的。 解决问题相当于解决 问题，区分这两个问题的点在于存储箱的容量。例1: 命题1。如果，则存在最佳的解决方案其中所有的操作和定义的初始时间有正确的时移（即尽可能晚的预定的开始时间），其中开始时间定义为：。证明：让我们先来定义在一个最佳解决方案中的装载操作开始的时间窗口。 设为最佳解决方案，j,k是两个批次的货物，如果批次j在批次k之前操作的话，则记 为k批货物第一个操作的起始时间。这里有：由于 和表2中所示的各个场景（根据表2所示的结构性能）的定义所示。请注意，AJK的值为已知或者t属于相关的时间窗口时，目标函数的值不变。还要注意的是上，绑定的每个时间窗口的开始时间tk，1，想对于 始终是固定的。并且有：因此，我们可以得出这样的结论：如果问题是可行的：因此，我们可以根据性质1，正确的调节每个批次的操作时间和修复它的起始时间。这导致定义的一段固定处理时间间隔为每个一批计划罐（图4）。因此，我们得到了部分命令设置的时间间隔，使得：和。意味着首批J一批k之间，j和k是平行的。二进制顺序批与批之间的关系是一个很有趣的所有制问题所考虑的已知的固定间隔调度问题。然而，我们的问题还是一个没有理论解决调度问题。此属性的主要优点是：无论怎样调度，都能保持有效。因此，建模在优先级/继承批与批之间的关系变得有效。我们把这种问题建立成有权重的模型问题，我们通过在图中找到一个最优最小点来解决问题。引理2.2：这种问题可以在有限时间内解决，当时。证明：我们必须表明，问题是可以解决的，通过在有限时间内找到一个最小成本上的完美匹配赋权有向图。让我们先来详细说明如何此图是如何构建的。Let O, =1 . L, be ctitious initial intervals and F, =1 . L,be ctitious nal intervals. These ctitious intervals are used tomodel the initial and terminal states of the tanks. The ctitiousinitial intervals are characterized by a shampoo family identical tothe one of the last stored batch in the previous planning horizonwhile the ctitious nal intervals are associated to a dummyfamily. We have:令为虚构的初始间隔和为虚构的最后时间间隔。这些虚构的时间间隔被用于创建初始和终端状态的模型。虚构的由相同的洗发剂家庭的其特征在于初始的间隔在以往的规划视野上次存储的批量之一而虚构的最后的时间间隔相关联的一个虚拟家庭。我们有：此外，所有这些批次相关的N个时间间隔和他们的家庭是相关联的。设G =（Vpred，Vsuc，A）是一个与Vpred和均衡二分图的两套顶点和甲组的圆弧。 Vpred包含了所有的时间间隔，可以是其他的时间间隔的前身。根据不平等方程（2）及（3），它含有L虚构最初的时间间隔O和n批处理间隔。 Vsuc包含了所有的时间间隔可以是其他的时间间隔的接班人，因此，根据不平等方程（2）及（3），它含有虚构的最终间隔F和n批处理间隔。因此，我们有：让j和k为两个顶点，根据部分排序，我们用弧将这两个顶点连接在一起，如果j和k属于不同的家庭，那么该弧有一个权重S。 接下来我们将介绍的是通过表G中一个最小化成本机器调度操作，我们可以建立一个解决Pol问题的最优方案。我们可以按以下方法进行后续的计算。从一个虚构的初始间隔O开始，我们选择合适的匹配弧，从而创建一个路径建立一个虚拟终端间隔f0。因此，我们获得对应至L批处理序列的L路径的一组缓存区，这样，这些路径的总成本是总的安装成本。让我们举一个简单的例子，包括两个缓存区和3个批次。表3提供了详细的实例。让FI1和FF1（FI2和FF2）分别为和缓存区T1（T2)有关的虚构的初始和最终的时间间隔,1,2,3是批处理的时间间隔。根据顶点集的定义，我们有vpred = FI1，FI2，1,2,3和Vsuc = FF1，FF2，1,2,3。表4提供了弧A的集合的细节设置，以及其中每种情况如果存在的话，相应的弧成本。这种情况下的最优解，即在这个最小成本的完美匹配的有向图，示于图 中5。这个完美匹配的PL0问题的最优解如图 6所示。现在，我们将显示一个最小成本的二分图G的完美匹配，相对应的PL0问题的解决方案。设M是G的一个最小成本的完美匹配，sol是根据上述进程获得的相应的解。由于M是一个完美的匹配，所有的顶点饱和并且弧是独立的。这意味着，所有的批处理间隔是包含在L路径中的，每批间隔只能被分配给一条路径作为尾弧以及下一条弧的头弧。现在假设图G有没有完美的匹配M。因此，它是不能保证至少有两个饱和的顶点（由于jVsucj = jVpredj）。我们必须表明，在这种情况下，没有可行的解决方案解决该PL0问题，并且，至少有一个批处理间隔仍然在计划外。让我们说明，剩下的两个顶点不符合虚构间隔的要求。根据虚构间隔的定义，我们有：根据公式（6），每一个顶点对应的一个虚构的最初的时间间隔是由弧连接每一个顶点Vsuc的。这也说明，根据公式（7），每个顶点对应的一个虚构的最终间隔是由一圆弧连接的每一个顶点。这意味着，一个虚构的时间间隔不能在两个不饱和的顶点之间，因为有一个独立的弧将其连接到所有其他顶点。因此，剩下的顶点是批处理间隔，这也就意味着没有可行解。现在让我们来证明由最小成本的完美匹配M建立的解决方案是最佳的。假设Sol不是最优的，让置换构造（J，K）是两个批次j，k的置换批次，分别分配给存储箱L和L，从而降低设置总数。 让PR（K），SC（k）和FM（K）的前身，继任者和家庭的批次K，K = 1，. n。我们还由c的成本的圆弧欧塞尔，K表示的“j 2 Vpred，K 2 Vsuc.如果FM（J）= FM（K）没有改善是可能的。因此，我们考虑的情况下，其中fm（J） - FM（K）。在这种情况下，可以出现至少一个改进，如果：或者让我们考虑在第二个案件中，置换构造（J，K）改进了该解决方案。在这里，如果我们假设存储箱的顺序为路径，弧aj，sc（K），apr（K），J，apr（j），K，AJ，SC（K）增加当apr（K），弧AJ，SC（J），apr（J），J，K，AK，SC（K）被删除时。M是这样一组弧的集合：很明显，M0是一个完美的匹配，因为增加的弧是独立的，饱和的顶点在弧从M中删除之后也变成不饱和的。因此，根据方程（9）有： M是不是最小成本的完美匹配G的解，存在矛盾。因此， POL问题（12吨，20吨,对任给l=1,2,.,L可以在 的时间限度内用最小成本的完美匹配方法解决。 2.2.2 例2: .在这里，我们考虑的是至少有一个包含两个批次的存储箱的PL0问题。在这种情况下，容量为24吨容量的存储箱上的装载作业的开始时间取决于两位前辈，如果他们分享同一个家庭的定义，表1中的第四条规则。因此，前面模型的情况，基于二进制的优先关系将不可用。此问题可被建模为一个轴向，三个指标的分配问题（Burkard公司等，2009年，第10章）。概括来讲，如果max = 1 . LB 2 （Z），Z与Z非负积极行动整数，我们可以模拟一个z-index进行分配的问题。虽然多指标的分配问题是NP难题，复杂的至少有一个容量为24吨的存储箱的问题仍然是一个未解的问题。但是，我们的直觉让我们期望它也NP-难的。不过，我们可以声明存储分配批次已知时那些财产是可以利用的。命题2:如果各个批次在诸多存储箱上的分配时已知的，如果存在的话，那么各个存储箱的特殊调度是所施加的一个的固定时间间隔的排空操作。 在这种特殊情况下，每个排空机上的序列是排空操作的固定的时间间隔强加给的。加载机上的序列是从排空机直接推倒过来的。3:解决方案算法在本节中，我们专注于解决由包装服务公司所给的问题，也就是我们给出当存储区容量为24吨时的特定问题的算法。这里，批处理的排空操作的是一个固定的间值，必须在重新开始，其完成时间是： 。因此，一个批处理的装载操作的开始时间的定义是那些列于表1中考虑完成时间，和启动排空操作的时间是数据，而不是变量。3.1 第一个解决方案的算法：第一种算法是一个耦合到本地2-OPT的邻域搜索的基础上的贪婪算法。根据性质2，本算法的主要思路如下：一个系列的批次，增加值的发布日期排序由RK，2，建成并在该列表中的每个批处理被分配到第一个可用存储箱，不需要清洗，如果存在的话。否则，该批次分配给第一个可用的存储箱，将不可避免地清理旁边的X批次的家庭。在这里，X是可用的存储箱的批次。因此，要对X批次做一个预测：所选择的槽即将被清洗，如果最后分配的批次所属的家庭没有出现下一个X的列表中。如果上述两个情况下都不会发生，然后当前批次被分配到第一个可用的槽。如果没有可用的坦克，该批次释放，增加值排序的列表不定期分批Llate，提前期RK，2。被修复的计算的解决方案，如果它是不可行的。选择第3.4节中描述的方法。如果修复成功，并返回一个可行的解决方案，进行当地搜索就可以了。这种贪婪算法的框架，需要的时间复杂度为，在算法1中给出。算法1： 3.2 第二个解决方案的算法：HSACO第二个建议的解决方案上的蚁群算法是基于COLONY优化（ACO）的方法，它使用的模拟退火搜索跟最初提出的方法相似。该算法为双机流水作业了给出了很好的调度结果。蚁群优化是一个自然启发式算法，在启发式算法的基础上模拟蚂蚁搜索事物的行为。蚁群寻找食品行为的效率，这是基于：（1）大规模勘探面积，周围的蚁巢;（2）间接通信。至于经典的ACO启发式算法（Dorigo等Stutzle，2002年进行了全面的调查，这个超启发式），尝试构建蚁群算法的解决方案，以运行具有建设性的程序。 此后，我们提供有关蚁群算法的详细资料。信息素矩阵模型的批次的优先级，即，K元素SJ，SJ，K 2 SMIN，SMAX，是有一批k为继任者的一个很好的解决方案在同一个容器中的首批J的概率。因为有些批次重叠，并因此将永远不会被分配给相同的罐的信息素矩阵是稀疏矩阵。所以，SJ元素，k是不能为空的，当且仅当所有的表5中的规则需要被满足的时候。要注意的是，如果一个元素SJ，k是按照第二个规律规定出的，继承的批次K表的首批J的解决方案可能取决于上批与上批处理器j为在表1中所指定的第四属性。在每次迭代过程中，每只蚂蚁通过就近的贪婪搜索方法构建了一个解决方案。在一个基本的ACO启发式算法中，根据蚁群算法的规定进行迭代：在每个步骤中的选择被安排在一个批次存储箱中。通过使用集约化模式的多元化模式。在加强模式下，一只蚂蚁在所有的选择批次k可以被分配到的罐，与批处理的最高值与J，K SJ最后一批定于存储箱中。多样化模式的选择是由所分配的批次使用的是经典的轮盘赌选择过程。通常这样做的一个模式的选择根据一个固定的过渡概率为r：较低的r的集约化模式将被选中。在我们的SACO启发式抽动我们改变这个基本的选择机制，利用模拟退火启发式的主要特征：即温度变化过程。这里，在一个ACO启发式它被实现，通过使沿迭代演进，在这样一种方式，在溶液过程的开头的蚂蚁更经常使用的是多样化模式也就是集约化模式结束时的过程。这一原则已经被成功地应用到其他的双机流水作业问题中，在目前实现的SACO中， 已经为变量r测试了四种变差函数：第一个功能是F1，国际热核实验堆的当前迭代次数，以及ITERMAX的最大迭代次数。f1的曲线示于图 7中。这个函数的算法使得集约化模式构建解决方案时选择更具趋势化。它引导的研究加上早期的迭代，然后迅速增加强制选择集约化的函数值模式更经常地在建设过程中。第二个函数f2（ITER）（图8）平衡使用两种建设模式的整体迭代。该算法更适用于多元化模式，更经常的迭代次数在上半部分和下半部分的迭代成反比。在上半年的迭代中经常使用多元化模式，下半年的迭代则常使用集约化模式。图9中所示的功能3的行为是由函数f1产生一个相反的行为。算法通过多样化模式探讨了解决方案的很大一部分空间上的迭代。随之，西格玛值迅速增加。最后的函数f4是一个常数的函数。r的值被固定为0.6，因为它提供了最好的实验结果。对于SACO启发式算法的每一次迭代，如果还没有建立可行的解决方案，但我们对最好的那个未完成的解决方案进行一个最好的修复：尝试将每个未分配的批次插入到最好的存储区中。这里，最好可用的槽定义为可用的槽插入后最大限度地减少了安装成本。这种修复方法的成功在于使我们能够利用所有迭代的结果，从而提高算法的收敛速度。在每次迭代结束时，用于HGREE算法中的本地邻近搜索被应用在由蚁群算法求出的最优解中。最后，在下一次迭代前更新信息素矩阵。该SACO启发式算法停止后已达到给定的迭代次数。时间复杂度为。3.3 第三个解决方案的算法：第三个算法利用引理2.2中的说明，是基于约束松弛的结果。这个解决方案的算法的主要思想在第四属性的表1中，以获得一个二进制的顺序关系上的批次间隔，然后解决赋值引理2.2中所描述的的松弛问题。松弛问题的解决方案中可能包含不可行的分配：向存储槽中分配部分批次，但不满足问题（表1）中规定的第四属性，称为不可行批次。把所有不可行批次从该溶液中除去，并将未分配的批次添加到列表中。之后，在第3.4节提出的修复方法被施加到列表中。如果修复方法返回一个可行的解决方案，在本地搜索中应用到它。经典分配算法相当于原启发式算法的复杂性，时间复杂度为3.4 修复方法算法HGREE的修复方法是基于动态优先级规则对列表中未分配的批次进行排序，确定将其插入存储箱的一个最佳的插入规则。要做到这一点，我们定义了两个插入方法。第一，由1 - 传送，表示直接插入k到序列，如果可能的话。第二，插入的顺序坦克搬迁后的已分配的首批J k到一个未分配的批次。后者必须一定插入到序列另外的槽中，实现插入批处理。显然，从罐前除去首批J批处理插入是没有可能的，因为时间间隔IJ和Ik的重叠或与清洗操作（即设置）的其中之一重叠。未分配的批处理的优先级反映了将其插入到罐的序列的方便程度。它被定义为使用上述定义的两个运营商可能插入的数量。因此，该批次就越少（最低优先级值）被插入。可能是插入较少劣化的目标函数，该算法选择一个，这一个被称为最佳插入，其它批次的优先次序用更新后的插入来实现，该算法停止，当所有的未分配的批次插入或者批次不能被插入。在最后这种情况下，我们认为，修复方法不能修复不完整的解决方案。4. 计算机仿真实验在本节中，我们通过计算机实验运行来评估所提出的启发式算法的效率。让我们用贪婪算法加上本地搜索（算法1），HSACO的SACO启发式算法（算法2）在分配问题的基础上加上修复方法和本地搜索（算法3）来表示。首先，我们的实验实例要尽可能接近工业过程，以评估该算法的有效性。然后，在第二步骤中，我们对更多的随机实例上的算法的行为进行评估。对那些已经对比过的几种算法进行初步的实验，从而优化它们的行为。这些算法的不同在于：（i）蚁群算法在建立一个解的过程中的概率函数（ii）该应用类型的蒸发和执行过程，（iii）修复方法的影响（）的其他参数的值，如最大迭代次数和蚁群的大小。 概率函数，在算法2中由funproba（）表示，影响到全球的蚁群搜索策略。在经典的蚁群搜索算法中，这个函数返回一个恒定的值，即一个该算法的参数。在HSACO中我们对模拟退火算法采用同样的原则，即沿着搜索放向我们使概率各不相同。我们的想法是在开始搜索时多样化，并在搜索结束时集约化。这个实现的功能的测试是在3.2节中提出的。 研究的第二个参数是发散和执行过程中的类型。我们通过比较两种模式中的几个参数值来比较这两种模式。第一模式下使用的是百分比的信息素，而在第二模式下使用一个固定的数量的信息素的通过执行过程添加，并在发散过程中删除。 我们还研究了的修复方法对解的质量以及计算时间的影响。我们测试了以下值：q= 0时，q = 1，Q = 30，Q = 60，最好的非完全的解决方案。最后一个研究的参数是蚂蚁的数量和的迭代的次数。对于第一个参数，我们测试了三个值，而对于第二个参数，我们测试了四个值，实验结果表明，概率选择和发散及执行过程的方法有关。最好的结果在函数f2（图8）中，一个固定的发散量定义为s =（SMAX SMIN）/ ITERMAX）。q = 60的修复方法则提供了更好的结果，没有降低所需的CPU时间，因为主要是建立在第一次迭代的HSACO不可行的解决方案的基础上。此外，最合适的蚂蚁数目为20，最大迭代次数等于150.HSACO的启发式算法提供了最好的结果，我们评估了三个启发式算法的质量。 4.1 工业实例 首先，我们比较这些算法的工业实例，即尽可能接近到工业过程的情况下（出于保密的原因，真正的工业情况并不适用于广泛的测试目的）。在这种情况下，批次的数量大约是80：我们产生的批次大小约是75，80，85和90。对于每个批次大小，500的实例已被随机生成，并试图尽可能接近工业实例。为了这个目的，比率R1，R 1 =（存储箱的批次/家庭的数量），和比率R2，R 2 =（存储箱的批次/数量的家庭数量），跟那些工业的实例保持一致。生成过程的细节如下：比率R1随机生成，比率R2被设置为3。这意味着，存储箱的数目取决于批次的数目和需要的时间间隔内的整数值20.45; 33.75及家庭的数目的值的集合25，26，28，30。处理时间的压力p1（存储箱的装载时间）和pk，2（存储箱的排空时间）为1440分钟，这是将所考虑的阈值作为分数。这是为了让数据接近现实生活中的实例。 受限制的家庭设置时间被设置成25分钟。为了生成的预备期RK，我们随机生成包装生产线上的批次的序列，以便平均每生产线有R1批次。如果同一个家庭的两个批次的连续在同一生产线上，则没有空闲的时间被插入到这两个批次之间。否则，将被插入30分钟的时间。从这些时间表，我们推断出的值。 要评估启发式算法的效率，我们采用的是相对偏差REL（百分比）和绝对偏差ABS比较法。以达到最终对最优目标函数值之间的比较，和由给定的启发式算法计算出的目标函数值相比较，我们提供平均和最大偏差。这些偏差只能找到一个成功的可行的解决方案。我们通过对实例进行计算，记下最好的，一个启发式的实例提供了最佳的解决方案的情况下：本启发式算法提供相同的成本，包括在每一个启发式算法下的价值，最重要的两个启发式提供相同的最佳成本。 表6提供了最好的解决方案，是由启发式算法提供的百分比。第一列包含产品的批数，下一列提供最好的解决方案，每一个启发式算法的百分比。因为它出现在这个表中，启发式算法执行的其他启发式和回报率高达98.74较大的情况下最好的解决方案。HSACO提供了更好的启发式方法，但仍然坚定地占主导地位的启发式哈西数的最佳解决方案，计算的结果存放在表7和表8中，提出启发式返回的解决方案的质量上的计算结果的比较。表7给出了结果的相对偏差，而表8给出了结果偏离度的绝对值。这两个表的第一列是包含的批数。 正如预期的那样，给定的百分比结果的最佳解决方案，启发式算法给出了最好的结果。请注意的是，在测试的实例中，我们计算的平均百分数上升到11.14。此值由ASSI启发式返回的解决方案的质量上有直接的影响：当不可行批次的数量等于零，轻松的问题的解决方案是可行的，是最优的。然而，只要增加批次的数量，质量的解决方案更多地依赖的修复方法。我们清楚地看到的偏差能达到13.39，而平均偏差几乎等于零。 将一个实例中不能找到一个可行解决方案的百分比列于表9中。HSACO的启发式算法提供了最好的结果，因为它总能计算出一个可行的解决方案，而HGREE和哈西则未能解决某些情况。比较HGREE和哈西，我们观察到哈西产生更好的效果。表10给出了平均计算时间，以秒为单位。4.2 随机的情况下在前面的章节中，我们提供了解决真正的工业问题情况下的绩效评估的启发式算法。为了建立一个更一般的评估效率的启发式算法，我们已经考虑了不同的方案，在生成实例的方式中，与成为工业问题无关。即使我们不考虑一个完全随机数据生成计划，提供一个覆盖大范围的情况。此外，存储箱的处理时间，装载时间不再是不变的：每个批次都有其自己的存储箱装载时间。现在，我们给这些无规状实例生成详细信息。对于工业实例，实例的大小保持在75，80，85和90之间的批次。我们引入一个参数R用来建设一个大型的比率R1。至于工业类似实例，随机抽取的比率R1，使用均匀的规则上允许的可能值的集合。该集8R，9R，10R，11R，R 2 2.5 3 3.5 4，为R1导致考虑5个集合的4个不同的值。这些值将对应于数个不同系列的洗发水，并分别等于75，66，50，25的批数。我们保持一个恒定的设置时间，因为他们在这个问题上是依赖于机器的。要模拟一个变量的设置时间，不同的装载作业的处理时间。我们确定了一批处理时间相关的装载作业，通过从区间中随机抽取值。除了根据每个包装线的批次的平均数目绘制表格外，集合8，9，10，11为工业类似实例生成数据的其余部分。通过结合五个值的系数R和四个值的比率R2，我们得到20类（R，R 2）的实例或每个批次数目。如果在这些类别中的每一个中，我们生成100个实例，如上所述，最后共随机生成8000个实例。值得注意的是，一些生成的实例可能是不可行的。我们使用了启发式规则，很简单，放弃大部分的情况下尽可能。只要是被丢弃的一个实例，另一种是产生阶为O的8000个实例。值得注意的是，未检测到不可行的情况下，可能会保持在生成过程的结束。分析所得的结果是，我们已分组的类别的实例行为的算法时间是非常接近的.我们得到7类实例