用来减少库存和运送成本的制造商供应链调问题

1、用来减少库存和运送成本的制造商供应链调度问题摘要 在供应链中，制造商在不同的时间点从供应商接受任务，并且生产和提供给客户的最终产品是分批进行。供应链中制造商可以被建模为在一台机器，要解决的问题可以建模为最小化的加权流动时间的总和最小的批量交付成本。由于问题的任意处理时间，释放时间和权重是很难确定的，我们先分析一些多项式可解的特殊问题。这样，我们 开发一个启发式算法来解决一般问题。我们还开发了一个下界研究 ，我们的启发式算法和计算实验的表现证明，解决方案的启发式算法接近最优解。1. 介绍 供应链管理已经成为一个最重要的在制造业研究主题。这在束缚生产和外向交货同时考虑调度模型可以提高供应链的整体性

2、能。最近 供应链调度的新兴研究领域试图解决这个问题。爱尔和波茨（2003）的研究几种供应链问题，通过包括快递费用，除了总体目标中的调度费用。所有这些文件，考虑的目标最小化加权流动时间的总和（或流动时间之和），其中加权流动时间可以理解为持有存货成本。如果我们考虑一个单独的生产系统（或组织）作为一台机器，并且在时间的订单（或生材料）到达系统释放时间，那么问题将相当于单台机器释放时间上成批调度问题。如果其处理完成，任务可以交付给客户。在大多数情况下，已完成的任务给客户时，产生快递费用。因此，作业批量交付给客户节省快递费用。然而，等待 在系统交付工作增加了持有成本。因此，我们需要找到增加的库存持有成本

3、和降低的交付成本之间的权衡。赛维约翰和斯特尼（2009）研究这个问题在与多个客户的供应商，在这个研究中所有的工作都可以在时间为零时处理。他们提出 1.5近似算法，并进行参数数据分析来证明，该算法产生的解决方案更接近现实问题的数据的最佳解决方案。哈利姆和大田（1994）的研究成批处理调度，尽量减少制造商的流动时间，任务到达时和最终产品交付是遵循准时制生产的时间哲学。在本文中，我们研究了制造商的分批排序，在这的工作是在不同的时间由向供应商提供的，并 imi-1还有每次招致的交付成本交付向客户，并且每次向顾客分散货物都会产生一个分配费用。因此，我们的问题定义如下：我们对m顾客给出一组总做变量J=(S

4、1，S2Sm），其中Si=(Ji1,Ji2Jin)是客户Ii=1,2m设置的工作，任务数是n= n 。大多数实际案例中，对于制造商m是相对稳定的。这证明了我们的假设，即客户的数量m是固定。Jik 表示顾客Ii的第k个任务。对于每个作业Jik 记为 Pik,rik和Wik 。分别是处理时间，释放时间和权重。只有属于同一顾客的作业可以在相同的批次被传递。对于顾客Ii, 每个批次是一个交付成本qi,i_<m。我们的目标是找到一个时间表最大限度地减少了持有及快递费用的总和。在调度中，任务的单位持有成本Jik称为权重Wik 。系统中的时间段Jik 称为流动时间Fik。因此，系统中的持有成本Jik=

5、（Wik*Fik）。让Cik作为完成时间Jik 。然后，我们知道了任务Jik的交货时间Dik大于或等于Cik并且Fik=Dik-rik。延伸这三个符号，该问题可以通过以下方式来表示1|m，ri，k|Wi，kFi,k+biqi, 其中bi为客户Ii的批量数目的时间表。我们还作如下假设：（1）一旦任务被启动， 它的处理过程中不允许中断；（2）所有数据非负整数；（3）所有数据都为在零时前明确定义；（4）快递费用是独立的成批处理。 莱森等人（1977）证明了单台机器的随机释放时间的排序，以尽量减少总的完工时间和是非常艰难的。进一步，莱博等人（1984）证明单台机器的随机释放时间的排序以尽量减少总的完工

6、时间和是非常艰难的，即使抢占被允许。因此，很明显我们的批量调度问题即使是在允许被抢占的情况下也是很困难的。艾尔和波茨（2003）的研究相似问题的假设是相同的客户的工作遵循一个固定的作业序列。他们解释释放时间供应商交货的订单到达时间，问题的动态规划算法的时间复杂度为O与工作具有相同的权重。事实上，它们的动态规划算法给定的作业序列可以很容易地修改了当作业具有任意权重问题。我们 对于这个问题的第一项研究就是找出一些特殊情况下可以解决的多项式。那么对于一般问题我们开发了启发式算法，开发下限测试该算法的性能。本文的结构如下；第2节讨论一些这个问题的初始问题。在第3节中，我们研究最佳方案，当所有作业的作业

7、顺序是固定的。第4节研究这个问题时，每个客户的工作必须根据一个固定的排列的单台机器上加工，分两种特殊情况下（i）当所有的工作都有平等的处理时间，（ii）当所有的工作都处理单位时间。第5节研究了一般的问题，即任务有任意加工时间，权重，和释放时间。一种启发式算法和下界算法，并依据给出了计算实验表明，该启发式算法找到接近 最优解。第6节最后为结论，以简短的讨论未来的研究。2. 初步行动在传统的批处理调度（波茨和库里，2000），相似的任务被分组在一批次并被处理，缩短机器处理相似任务所需的那些设置成本/时间。在某些问题中，同一批次的任务可能不会需要被连续地处理，并且我们称这些问题抢占处理批量。很显然，

8、在传统的配料问题，同一批次的作业连续加工缩短机器设置时间/成本（如图1）。因此，传统的批调度问题不允许分批抢占。在我们的问题，我们假设设置的时间顺序是独立的，因此可以连接到每个作业的处理时间。因此，设置时间包括在处理时间。然而，我们的批处理作业，以节省批量交付成本。因此，不像传统的批调度问题一个批次使用一台机器设置一个作业组进行处理，在我们的问题批次是一组任务在单货交付给客户。第n批量第一批量第二批量图1.0传统的批调度问题没有批抢占考虑图2给出的解决方案，属于顾客Ii的任务J4,Jn-2,Jn-1和Jn 单批次交付，因为J4的持有成本的增加是由于其在系统中的等待完工时间Jn抵消了保存的交付费

9、用qi。 图2.0供应链调度当M>1时客户和批抢占图3.0分段和主要任务的时间表 经过J4处理后，属于其他批次的任务被处理和传递，因为Jn 只释放在整个时间表的末端。因此，在我们的研究中，同一批次的工作不被连续处理，批次可能被抢占。备注1.批次抢占的制造商的问题（i）当所有的释放时间是零或（ii）当只有一个客户时，不存在一个最佳的批量解决方案。需要注意的是，当有一个以上的客户和任意工作释放时间，然后用无批抢占批次解决方案可能不是最佳如前所述。考虑一个时间表a=J1，J2，.Jn ，在其中任务Jn是在处理过程S中的第K个任务，Jk可以是属于任何顾客Ii（i=1,2，.m）的任务。如果Jk-

10、1在Jk释放前完成，在任务Jk的处理开始之前可能会有空闲时间。我们称任务组之间的两个连续的空闲为时间段，在一个阶段的第一份个任务是整个阶段的最主要的任务。例如，在图3，有阶段中的调度。J1，J4，Jn-2分别是第一阶段，第二阶段，第阶段的主要任务。 在命题1-3，我们提出了一个最优的简单属性日程表。命题1.如果机器闲置在时间t，存在其中一个最佳的时间表，则（1）其中为t后完成的任何工作，必须在t之后启动。（2）在t之前开始的任何作业，必须在t之前完成。命题2.存在其中一个最佳的时间表，如果作业Ji，k 在时间t完成，那么一定要在客户Ii的第一交付交付批量或者t后。命题3.其中存在一个最佳的批次

11、排程 ，每批交付（批次任务）的发生的时间完成时间及其最后处理工作。 在某些生产环境，由于一些技术上的限制作业都在一个预先指定的处理序列。例如，任务依据到达的顺序处理是为了简化材料处理。此外，对给定的固定作业序列知识可以开发启发式算法，解决一般的问题。读者可参考第5节，我们使用给定的固定作业序列的最佳批次，发展我们的启发式算法。因此，接下来的两节中我们研究这个特殊情况。第3节研究最优批次的工作顺序是固定的，我们称之为的所有作业的固定序列。第4节研究的最佳配料工作时每个客户的顺序是固定的，我们称之为固定客户工作序列。这里的固定顺序是指到达顺序， 也就是说，作业序列作为非递减次序的释放时间，无论是在

12、一个序列（第3节），或由于多个客户的多个序列（第4节）。3. 一个给定的固定所有在职序列的最佳配料 在本节中，我们研究一个给定作业的最佳批量序列，a=J1，J2，.Jn。不失一般性，我们可以假设每个客户Ii的工作，按照工作顺序a=Ji,1,Ji,2,.Ji,n。下面的两个引理让我们开发一个多项式算法解决给定的最佳批量固定所有在职序列S在O（n）时间。引理1.一个给定的固定全作业序列的最优批量问题，顾客m的顺序s，无关单客户的子问题，可以减少到m。证明.让我们假设a中的第一份工作是Jgh，i，e，J1=Jgh。Cgh代表Jgh的完工时间，可以使用表达式来获得，Cgh=rgh+pgh。让我们假设J

13、u-1=Jik和Ju=Jjl，对于任意的u=2,3.，n。然后Cjl=maxrjl，Cik+Pjk。因此，对于一个给定工作序列a，可以计算出任务Jji完成时间Cji，对于所有的（jl）对。由命题3，只在客户li的一些任务完成才向其交付。也只有同一客户的工作可以一起进行批处理。因此，一个客户Ii的工作批量取决于值Cik，Wik和qi，k=1,2，.，n。Wik和qi的值是参数，Cik是一个给定的固定值a。因此，客户Ii的最佳批量是独立于其他客户批量额解决方案。因此，客户m问题的最佳批量，可以通过求解求解M单客户的子问题。需要注意的是固定所有任务序列的优化批处理调度的总成本是m个单一客户的总成本的

14、总和的子问题。引理2.对于任何给定的固定所有任务序列s，对于任何单一客户的子问题批量解决方案的最优，对客户li来说，可以在时间O内获得。证明.让客户li的任务在给定的a中为ai。由引理1，对于客户li的最佳批量是独立的其他客户批量的解决方案，在给定的a中Cik的值，对于所有的（ik）对是可以计算的。因此，我们需要对客户li找到最优的批量，通过给定的ai，Cik，Pik，Wik和qi。让我们称这个问题，客户Ii的原始问题。现在考虑客户li的任务序列ai=ai。加工时间Pik=Pik，Wik=Wik，qi=qi，rik=Cik-pik。很显然，在任意时刻t，所述一组作业完成在最佳修改后的问题的原问

15、题和时间表将是是相同的。因此，对于客户li获得最佳的批处理调度， 在这两个问题（）。1|Pik，Wik，rik，ai|WikFik+biqi。(ii)1|Pik，Wik，rikai|WikFik+biqi将会是一样的。赛维等人（2012）提供了一个多项式算法的时间复杂求解最有批量问题1|Pik，Wik，rikai|WikFik+biqi。因此，证毕。现在，我们给的最佳批量算法，算法A1给定所有任务序列。算法A1。对于给定的任务序列a的所有任务，计算完成时间如引理1。通过赛维等人的算法来解决1|Pik，Wik，rikai|WikFik+biqi，下一个i。因此，我们有以下的定理。该定理1.算法A

16、1上找到任何批量优化解决方案鉴于O时间固定所有任务序列。MI=1MI=1证明.由引理1，算法A1找到最佳批量解决方案。在时刻O发生的a中的所有的(i,k)对的完成时间Cik 的计算，原来的单一客户问题转化为修改单一客户的需要问题 O（ni）=O（n）。由引理2，顾客m的最佳批量满足 O（ni）=O（n）。因此，A1算法的复杂度为O（n）。4。一个给定的固定客户作业序列的最佳批量。在第3节中，我们证明了当所有工作遵循一个固定的工作序，最佳批量配料可以在O（n）的时间内解决。在本节中，我们研究工作批量时客户Ii的任务遵循 一个固定的作业序列ai（i=1,2，.，m）。在下面的定理，我们证明这个问题

17、即使在单位处理一次作业时，客户数m取任意值时也是很难的。备注2.我们知道WikFik+biqi=WikDik+biqi-Wikrik，其中Wikrik是一个常数对于给定的问题。因此，释放时间可以计算总成本时被忽略，从所有可行的时间表中选择一个最优调度。在本节中开发动态规划算法忽略释放次成本计算。 定理2.作业的最佳批量时，每个作业序列客户是固定的是很难的，即使所有的作业需要单位处理时间。证明.当顾客li的工作遵循固定的作业序列ai（i=1,2，.，m），这个问题可以看作是批量在M-链给予优先关系的工作。让我们考虑问题，哪些工作需要处理单位时间和批次快递费用对所有客户是零。可以很容易地看到，这个

18、问题的最优调度在单个作业在每个批次。因此，寻找一个批次排程，以减少批持有成本和批量交付成本。WikFik+biqi，等价于找作业的时间表，以尽量减少加权流量作业时间总和WikFik。因此问题等价于1|Pik=1，Wik，rik，链|WikFik问题。菅直人（1980）已经证明这个问题是难得。1|Pik=1，Wik，rik，链|WikFik问题，Lenstra和RinnooyKan 研究的问题可以多项式降低处理单位时间的工作批 3mm+12m+23m调度问题1|Pik=1，Wik，rik，qi=0，ai|WikFik+biqi。因此，固定客户的工作序列与客户的任意数量的批量是不难，即使工作需要处

19、理单位时间。它遵循从定理2的批量在给定的固定客户工作顺序是不难的，当有任意数量的客户。我们开发了一个动态规划算法，假设固定客户的工作序列的问题及客户有固定的数量。艾尔和波茨（2003）提供一个关于O（n ）时间的最佳批量动态规划算法，当作业遵循固定客户的作业序列，以尽量减少流动时间和交付成本总和。他们与在复发稍微修改算法关系也将解决这个问题，在同样的时间复杂度O（n ）以尽量减少加权求和流动时间和交付成本。在本节中，我们研究问题的批量有固定客户的工作序列。在4.1节中，我们开发了一个动态规划算法的时间复杂度O（n ），当工作有等同的处理时间，与处理单位时间工作第4.2节研究批量，并提供了一个动

20、态规划算法的时间复杂度O（n ）。4.1具有相同处理时间的任务本节中，对于所有的（i，k）我们假设Pik=P，除了客户的任务序列的假设。这种情况定义为1|m，Pik=P，ai|WikFik+biqi，其中P>0且是一个整数，ai是给定客户li的任务序列，i=1,2，.，m。引理3.考虑一个工作序列a=J1，J2，.，Jn。如果第段在序列a中是开始的第一项任务Ju，任务的总数量l，最后一项任务Jv。Jv的最后完工时间等于Ju+l*p。证明.我们省略了证明，因为它是简单的基础上的计算。mi-1由引理3，我们可以计算出任何段的最后工作的完成时间。例如，在图3中，在完成作业的时间J7=J4的释放

21、时间+4P。不是一般性，我们可以索引每个客户在其给定作业序列顺序任务。利用引理3，我们开发了一个动态规划算法，调度任务增加但是不违反不同顾客li的给定的任务序列ai。我们使用的状态表明一个类似于霍尔和波茨提出的（2003），其中意味着顾客li的第一项任务ki被调整了，k=ki ，顾客li的第一个未经调整的任务是，如果ki<ni。既然我们可以批抢占，有可能是一个悬而未决的批次为每个客户li在任何给定的时间t，其中一个悬而未决的任务批次是处理以顾客li的，但批处理将被传递到未来，处理完属于客户li一些工作后，我们使用状态变量来表示交付给客户的任务数量，任务是交给顾客li的。因此，在待处理的批

22、次的客户li作业是。状态变量解释了当前阶段的首要部的工作是，l是在当前阶段处理的任务数。需要注意的是si=ni意味着 所有作业已交付给客户li，意味着没有任务已经被调整或交付。 考虑我们得到状态的这种情况，附加任务到状态，在新的状态中，交付的任务数量是；当前阶段的主要任务是；当前阶段的任务数量是l。很显然。当我们追加到状态，可能会发生四种情况中的一种； 第一种情况.形成一个新的阶段，任务的完成要顾客lh的交付日期调整。我们得到，的完成时间=rhg+P。因此，相应的调整的总成本是其中；对于所有的，并且对于h=h，l<k有。第二种情况.形成一个新阶段，任务的完成不需要顾客lh的交付日期调整。

23、，。因此，相应的调整的总成本是其中对于所有的h=h，；对于所有的h=h；l<k有。第三种情况.不形成新的阶段，任务的完成要顾客lh的交付日期调整。最后一个阶段的首要任务附加作业之前还是，相应的调整的总成本是其中。第四种情况.不形成新的阶段，任务的完成不需要顾客lh的交付日期调整。最后一个阶段的首要任务附加作业之前还是，相应的调整的总成本是，其中kh<nh。 现在，我们提出我们的动态规划算法，算法A2解决问题。算法A2.边界条件；最佳的解决方案的数值；递推关系：定理3.定理2在时间维度为O固定任务序列问题当任务有相同的处理时间时，得到了一个较好的序列调度。证明.对于不同的k和不同阶段

24、中R，大部分和是不同的。在案例1和2中，存在不同于的m，l=1。因为k<n,m是固定的。状态数是。递归，案例1占主导地位的运行时间，它需要搜寻大多数首要任务中k不同于的，l中的k-1个值。这样案例1的运行时间是。因此，案例1和2的运行时间是。在案例3和4中，因为是是一个阶段的首任务，l是一个阶段的任务数量，对于我们最多有种组合，l状态是。对于每个状态，情况3需要O(n)运作来找出h（从1至m），（从0至kh-1）。（情况4只需要h次搜索），因此情况3和4的运行时间也是。因此，算法A2的整体运行时间是。该算法的正确性是直接服从以前的讨论。 作为扩展的讨论中，上述算法A2也可以是适用于其他供

25、应链调度问题具有固定客户的工作序列和相同的处理时间，让调度措施是，这是任务Jik完成时间Xik的一种单调非减函数。我们这样表示问题，在这里为简单起见我们省略工作完成时间，使用代表任务的客观价值。为了实现算法A2，我们只需要修改如下的费用计算的递推关系。对于第1种情况，我们更换期为，其中是客观的价值，当在工作完成时间为。对于情况3，我们用替换，其中是客观的价值，当在工作完成时间为。情况2和4不需要修改。备注3.算法A2可以解决问题在时刻，其中是任务中的完成时间单调非减函数。4.2.任务和单位处理时间 在这我们假设对于所有的（i，k）对，Pik=1。我们需要找到最佳的调整批量当对于不同的顾客li给

26、定的任务序列。这个问题定义为。在第4.1节中讨论的相同处理时间问题，在任何任务处理过程都可以到达新任务。然而，当任务有单位处理时间，任何作业的处理过程中的不能任意作业的到来，因为到达发生在离散的时间点。任何作业的处理过程中没有任务到来的这一特性使我们开发出更好的动态规划算法的处理单位时间的问题。当所有的工作都有单位加工时间如下引理4可利用命题1和2表示的属性获得。备注4.对于任何交付批次排程，其中是第i个交货批的组任务，存在一个最佳的工作序列a*，此时机器处于闲置状态时间t，只当没有可用的作业在t时间进行处理，而不是违反给定的固定客户的工作序列。证明.让我们假设引理是不正确的。在a*中，对于批

27、量配送调整的BS，必须有至少一个t可以用来处理一些任务，但是设备在t是闲置的。让第一个这样的空闲时间为节拍时间t1。在加工时间t1至少有一项任务Jhk是准备好的，但是当t>t1时要调整。在t1时刻调整Jhk不会增加任务的完成时间，因此，强化了任何交货批量i的批量的交货时间。因此，在a*中任务Jhk在t1时刻调整。重复上述过程对于所有这些空闲时间的新的调整会给我们一个在工作序列没有机器闲置时间，当任务可以在不违反固定客户的工作序列。上述迭代过程不会增加批量的交货时间。这说明假设引理是不正确的。推理1.所有可能的批处理调度的最佳工作序列，将具有相同的最小完工时间的Cmax。考虑部批量的工作组

28、其中顾客第一项任务Ki必须被调整当。推理2.关于所有可能的批处理调度的最优工作序列对于部分工作组，有相同的最小完工时间。备注4和推理2仅用于处理单位时间的问题是正确的，任务不能在有加工任务时候到来。由于对于所有的批次调整的部分工作组最小完工时间是相同的，我们可以判断持有成本及任何最后一批交付的部分调整批量如，如果最后交付批量是顾客Ih的任务。在任何批次排程的最佳作业序列相同的最小完工时间的这种特性有助于我们制定一个动态规划算法。我们首先给出估计的程序对于任何给定的部分工作组。程序 CMAX 第一步；设，其中Jh是顾客Ih的链中第一项任务。第二步；如果，设；停止第三步；设，其中是Ji在L最小的释

29、放时间r处的任务。 设Ji的运行时间。第四步；设。第五步；从顾客li的链中移除任务Ji。第六步；如果li的链不是空闲的。 设Ji=顾客li链中的第一个工作且。第七步；重复第二部。引理5.对于任何给定的，程序 CMAX可以判断最小完工时间，在O（n）时间。证明.我们省略了证明，因为从给定的步骤的过程看很明显。现在，我们提出我们的动态规划算法，算法A3找到最佳的批量解决方案。算法A3.边界定义；f（0，.，0）=0最优值的解决方案；f（n1，.nm）递推关系：请注意，如果，顾客Ih的批量包括任务在之前完成。因此，提供了一批任务在，不可能是由命题3得到的部分工作组的最优解。定理4.算法A3找到最佳的

30、固定客户任务序列的最佳调度，在处理次数为的单位处理时间。证明.该定理的正确性遵循以前的讨论。可能有种状态，每一种状态需要O（n）次计算。所以运算次数是。正如在4.1节中讨论，算法A3可以进行修改以解决单位处理时间的固定客户任务序列的批量调度问题，对于任何目标函数，这是关于任务完成时间的单调非减函数。备注4.算法A3可以解决问题，当运算次后，其中是任务的完成时间的单调非减函数。5. 有任意处理时间和重量的批量 制造商的任意处理时间和任意权重进行批量调度是相当困难的。然而，在第3节中，我们对于给定的作业序列的批量提供一个多项式算法，ie，对于所有的任务固定序列。在本节中，我们开发了一个启发式算法模

31、拟任务序列和批量问题。我们采用分层算法中，我们生成基于遗传算法的工作序列，并找到使用任何给定的作业序列的最佳批量解决方案算法A1。在5.2节中，我们建立一个下界问题来测试算法的性能，并在第5.3节我们讨论我们的计算实验的结果。5.1.遗传算法 我们使用随机密钥遗传算法（RKGA）由豆（1994）提出。Selvarajah等（2012）用RKGA解决在一台机器在任意释放时间，任意处理时间，和任意权重环境中的批量调度问题。我们的单一客户问题使他们问题中的特殊情况，因此每条线路中的单元都被分配了一个客户号，即相应客户的任务号，以及一个随机数。任务序列是由随机数的非递减次序排序的工作所获得的。现在，我

32、们简要介绍一下我们的算法的主要步骤。人口序列.在我们的算法中使用的30人口规模，在我们的算法使用的30人口规模。每条染色体有n（任务编号）的基因，每个基因代表一个工作，被分配一个随机数。以随机的顺序而获得的染色体的作业序列数字。例如，考虑染色体的调度问题有3个任务。那么染色体将有3个基因。让分配给特定染色体的随机数是0.3基因1（J1），0.6为基因2（J2），和0.4（J3）用于基因3。那么该染色体的作业序列是J1，J3，J2。健康值。我们用算法A1评估了每个作业序列额最佳批次调度的总成本。家长的选择。人口是随机排列的。对于人口每名候选人，我们从第一候选人开始小计适应值。我们通过所有的30适

33、应值的总和把每名候选人的分类汇总。然后，两个家长都随机选择采用轮盘赌方法来生成两个新的关闭弹簧。临界.我们用两个交叉点，从中得到两个截然不同的随机整数，其中n是所有任务数总和。这两个数字将任何分裂染色体分为三个（或两个）段，如，。请注意，S3可能是空的。然后我们交换随机数选取对父母的S1和S3的相应染色体。交叉参数选择：我们用20个问题测试了交叉的概率0.7,0.8和0.9，发现0.8是最适合的交叉概率。因此，我们使用0.8的交叉概率。突变.对于交叉后得到每个染色体，从中得到两个截然不同的随机整数，交换这些染色体的任务。突变参数的选择；用20个问题测试了0.1,0.15和0.2突变概率，发现我

34、们的问题0.2最适合的变异概率。因此，我们使用0.2的变异概率。人口池；一个生成的孩子将被接受，只有当它的健康值（总成本）和人们以前接受的儿童或者当前的候选人不同。当50次迭代的最佳解决方案没有改善时，我们给一个随机抖动人口池。池的大小为90，其中包括60个新的儿童和30名候选人在当前人口。随机抖动；随机抖动是用来引入多元化的人口。在随机震动，用随机生成的染色体替换种群池的最佳人选。人口选择；该池是按照健康值非递减顺序排列的。新的人口的一部分将从人口池的前30人选择。我们设定一个随机数并选择最佳的k个候选人的从人口池。剩下的（30-k）个候选人随机的从最后的60候选人的人口池中选择。停止准则.

35、该算法当迭代次数超过1500时停止，或者随机摇动后，50次迭代的最佳适应值没有提升。遗传算法总结如下算法A4.1. 产生初始人口大小为30。三名候选人中的初始人口被设置为跟随SPT（最短处理时间）作业序列，WSPT（加权最短处理时间）作业序列，和LW（最大权重）作业序列。其余27名候选人随机产生。2. 使用算法A1评估每名候选人的适应值，并记录最佳人选。3. 如果随机抖动是必要的，那么对人口进行震动；回到步骤3。4. 如果停止条件满足后停止。5. 通过执行以下事项重新生成60个孩子； 选择一对采用轮盘赌方法的父母。 做交叉和或变异操作，如果可能的话。 接受新的孩子，如果它满足要求。 评估每个孩子的适应值用算法A1。6. 如果有一个孩子比候选人还要好，设置为那个孩子的最佳人选。7. 从大小30池中选择一个新的人。8. 回到第3步.5.2.下界让我们修改我们的多个客户的问题作为一个单独的客户和运费问题。 表格1启发式算法和下限算法当和时候的不同表格2启发式算法和下限算法当和的差别我们可以在修改后的问题删除第二个下标k，因为只有一个顾客，因此，修改后的问题可以通过以下方式来表示。需要注意的是修改后的问题只使用最小批量交付成本，并允许不同客户的作业在同一批次进行批处理。在第1节中讨论的问题，当抢占允许时是很难确定的。因此，我们使用改变的