最小化最大完工时间的两车作业交付并行机器调度

摘要

摘要以最小化最大完工时间为目标，处理了具有协调作业交付的并联机床调度问题。不同的作业在运输过程中需要不同大小的储存空间。该问题中的一个客户的一系列作业优先在两台相同的平行机器上处理，不抢占，然后由两辆车辆分批交付给客户。对于这个NP困难的问题，我们首先证明了除非P = NP，否则不可能有一个最坏情况性能比界小于2的多项式启发式算法。在此基础上，我们提出了一个多项式启发式算法，其最坏情况比为2。

1.介绍

生产和分销运作是供应链的两个关键运作功能;关键是要将这两种功能结合起来，以协调的方式共同调度，以达到最佳的运营绩效[1]。然而，在传统的调度问题中，总是假设有足够的运输工具来完成作业，而不需要运输时间。与传统的调度不同，本文研究的是两个阶段的调度问题，第一个阶段用于在两台并行机器上加工作业，第二个阶段用于交付使用两辆车完成的作业。

在集成生产和出库配送调度(IPODS)问题中，需要协调供应链各层次的调度、批处理和配送决策，以使整体调度和配送成本最小化[2]。在过去的二十年里，各种各样的ipod模型被广泛研究。陈(1]对这些模型进行了全面的调查。在调查的基础上，兴趣问题被认为是一个一般大小和有限数量的工作的IPODS模型。因此，在下面，我们只回顾几个密切相关的研究工作。近年来，在ipod模型上做了一些并行机器和等尺寸的工作，所有的工作都有相同的尺寸。例如，霍尔和波茨[3.研究了几款有足够车辆的车型。在他们的模型中，所有的成品都交付给一个客户。有多个客户的模型也在[4，5]。王及程[6]曾经研究过两个相同的平行机器和一辆车的模型，以使最大完工时间最小。在该模型中，由于预防性维护，一台机器上存在一个不可用的时间间隔，当机器恢复可用后，未完成的工作可以继续进行。他们证明了这个问题是NP-hard，并提出了一个最坏情况比为的启发式算法 ．最近，潘和苏[7提出了一种改进的启发式算法，其最坏情况比为 ．显然，对于工作通常有不同大小的模型，与涉及相同大小的工作的模型相比，它将相当困难地解决，因为批量决策现在涉及装箱，这是单独的NP-hard在强烈的意义上[8在不允许分批交货的情况下。张及李[9)率先建立了涉及一般规模工作的研究模型。根据他们的模型，在第二阶段，人们只能使用一种运送工作的车辆。他们提出了两个最坏情况比为的启发式算法和2，分别为单机配置和两个相同的并联机配置的机型。在此基础上，提出了几种改进的启发式算法。对于单机配置模型，He等[10和Zhong等[11提出了一种改进的启发式算法和一种在最坏情况下具有比值的最可行启发式算法和 ，在哪里ϵ是正的，可以是接近0的任意值;对于具有两种相同并联机配置的模型，Zhong等[11提供了一个最坏情况比为的启发式算法 ，和Su等[12提出了一种最坏情况比为的启发式算法 ，除了两种特殊情况。对于有多辆车的车型，Chen和Pundoor [13[进行了一项研究，研究的是一种车型有足够的车辆，其中所有的工作都有期限。为了使总运输成本最小，他们对该模型开发了一个启发式算法。蒋和谭[14]设计了一个多项式时间启发式算法，最坏情况比为2，适用于单机和两辆车的模型。然而，据我们所知，很少有人关注具有相同的平行机器和不少于两辆的有限数量车辆的模型。

我们研究的问题是Jiang和Tan研究的模型的扩展[14，其中第一阶段的机器环境从一台机器扩展到两台相同的并行机器。研究中存在的问题概括如下:对于一个客户作业数量为n彼此独立， ，每一个都必须首先由两台相同的并行机器中的一台进行非先发制人的处理，和 ，在一个制造系统中，然后交付给客户。工作 ， ，需要一段时间的处理在制造系统中有一定的规模哪个代表物理空间因为它是装在汽车里的。有两种同质载体(和 ）可用于交付最初在制造系统中已完成的成批作业。每一辆车的容量是z．这表明，在总尺寸小于的情况下，可以根据车辆的物理空间来安排已完成的作业z．一个交付批次是指由同一辆车一次交付的所有作业。一辆车需要一段时间T指在交付一批作业时的运输过程，即从车辆开始交付一批作业到交付后返回机器的时间。其目标是在制造系统中搜索处理作业的时间表，然后将完成的作业交付给客户，从而使所有作业所需的时间最小化N等待加工和交付给客户。为便于分析，计划的最大完工时间定义为 ．它是从一辆车完成最后一批交付给客户到它返回制造系统的时间。在此条件下，我们需要求解的是能使最大完工时间最小化的调度。

由于到目前为止我们知道我们是第一个考虑两个机器和两个车辆的模型，本文有两个目标。我们的第一个目标是分析我们的模型的计算复杂度，并提供模型所满足的一些最优性质。同样，类似模型的著名算法也不能解决我们的模型。所以，我们的第二个目标是开发一种针对问题的快速启发式算法。其余研究的组织如下所示2首先引入符号，以及感兴趣的问题的几个最优性性质。部分3.为感兴趣的问题提供启发式，然后分析最坏情况下启发式的性能。部分4利用的结论。

2.符号和预赛

本节首先介绍下列符号。这些符号在整篇论文中都是统一使用的:P:在一个制造系统中处理所有作业的总时间，即: ．至于日程安排δ对于这个问题，它被定义为 ：要交付的总批数δ．为每一个 ，我们定义如下: ：k第一批交货δ． ：批处理中所有作业的处理时间之和 ． ：车辆离开生产系统进行运输的时间 ． ：准备时间 ，表示完成分配给的作业处理的最近时间 ．值得注意的是，在任何可能的时间表中，都有 ．除非它是含糊的， ， ， ，和被简化为 ， ， ，和 ，分开。对于最优计划，它被定义为 ：最佳时间。 ：机器完成最后一个工序的时间。 ：交付的批次数量。

给出了该问题的几个最优性性质。由于条件的直接性，证明被省略了。

引理1。对于满足以下条件的问题，存在最优调度:(我)在任何机器上处理的作业之间都没有空闲时间(2)对于每个交付批，在同一台机器上处理的批中的所有作业都在该机器上连续处理(3)分配给一批并在同一台机器上处理的作业可以在该机器上以任何顺序处理因此，只有满足上述属性的调度才会被进一步考虑。

引理2。 ．
显然，我们的问题是NP-hard，因为这是运输时间的特例等价于求解经典的两并联机床最大完工时间最小化问题，该问题具有np困难。

引理3。除非P = NP，否则不可能有一个最坏情况性能比界限小于2的多项式启发式算法。

证明。我们通过以下PARTITION问题的简化证明了这一点，该问题已知是NP-complete [8]。
分区:n自然数 ，有子集吗 这样 ？
给定这个PARTITION实例，我们考虑这个问题的一个实例n工作, ，在哪里 作为一个子集 令人满意的可以达到。很明显，当且仅当该实例的最优调度中形成了两个批次时，上述PARTITION实例有肯定的答案。至于时间表，工作在 和 机器是分开加工的吗和然后分配给两个不同的批次，每个批次由一辆车交付，最大完工时间为 ．相反，对于任何子集的实例，它都需要三个批次或更多批次 令人满意的 ．其中一辆车至少交付两批货，因此相关计划的最大完工时间为 ．
对于最坏情况比界小于2的问题，假设存在一个多项式启发式算法。对于最优计划下的两个批次的形成，如所述，最优最大完工时间为 ．很明显，假设算法能够以最大完工时间作为时刻搜索最优调度当需要3批的时候。这应该是一个多项式时间算法在最坏情况下性能比的界限是2。因此，通过上述的约简，算法能够在多项式时间内解决PARTITION实例，这意味着P = NP，这与我们的说法相矛盾 ．
因此，对于该问题，除非P = NP，否则不可能得到最坏情况性能比界小于2的多项式启发式算法。

3.启发式

在本节中，我们首先介绍以下算法FFD (first Fit decrease) [15，是求解装箱问题的经典算法。在提出的启发式中，它将应用于组成批次。请注意车辆载客量(z)及工作规模( ）提出了FFD算法的基础。

３．１．FFD算法

步骤1:按照大小不递增的顺序对作业进行排序( ）第二步:分配大小最大的任务步骤3:为j= 2,…,n,如果j考虑最大的作业，然后将它分配给索引最低的批处理，这样对应批处理的总作业大小就不会超过z

引理4(见[16])。对于一个装箱的实例I，假设和对于最优解和使用FFD算法得到的解，我们有 ．

在下面，我们将提出一个启发式的问题，并分析其最坏情况下的性能。这个启发式的描述如下。

３．２．启发式哈

步骤1:使用FFD算法批量分配作业。假设成型批次的数量为 ．第二步:批量工作 ，计算处理它们的总时间并表示为 ，为 ．检索批以便 ．步骤3:批次从一个接一个地分配分配给在分配前负载较低的机器(将一批作业分配给同一台机器)。每批作业都是按照随机顺序排序的。步骤4:第一辆和第二辆车应该交付分配给机器的所有批次和 ．每辆车需要配送每批待发货的成品;在车辆可用的情况下，如果有多个批次完成，则车辆需要调度索引最低的批次。

首先分析了启发式HA的时间复杂度。因为大家都知道FFD算法的时间复杂度是 ，这需要时间在步骤1中;而且，它会获得所有的时间为在步骤2;作业批处理分配的成本最高在步骤3中，批量交付最多将占用在步骤4取决于 ．启发式HA的时间复杂度是 ．据推测表示启发式HA的最大完成时间。在启发式的求解中，设和表示完成最后两台机器中排序的作业所需的时间矩和 ．然后, ．此外,定义 ．

引理5(参见[9])。 ．
基于启发式HA，批按其处理时间的非递减顺序建立索引，并在批分配之前将批逐个分配给负载较小的机器。可以很容易地证明，每批具有奇数索引的产品被分配给机器由车辆运送 ；对于具有偶数索引的批，它们被分配给 ，然后用车辆运送 ．此外，与索引较大的批处理相比，索引较小的批处理的交付时间更早。假设x和y在使用启发式HA获得的解决方案中，分配给第一批和第二批作业的单独总时间，即，和 ．

推论1。 ； 如果 ．

证明。因为 ，为 ，根据第二步，我们有和如果 ，这意味着 和 如果 ．

引理6。 ．

证明。据推测表示使用最优方法将作业分配给批时的批数量，而不是使用步骤1中的FDD算法。很明显,有 ．与此同时, 根据引理4,这表明 ．

引理7。考虑了启发式HA实现的调度。(我)条件是一批存在机器这和 ，有 ，为(2)在这种情况下，那台机器是分批分配的吗这和 ，有 ，为

证明。(我)回想一下，批是按非递减顺序索引和交付的 ， ．请注意,和 ．自 ， 由引理1(我)。 ，有 ．因此,为 ．由此可见, ．重复使用同样的论点，有 ，为(2)类似于(i)。

推论2。考虑启发式HA获得的调度。如果 ，然后 如果奇怪的是, 如果是偶数。

引理8。如果 ，然后 ．

证明。

推论3。如果或 ，然后 ．

引理9。如果奇怪的是, ，然后 ．

证明。如果 ，然后根据引理8．现在,假设 ．的必然结果2， 如果是奇数。

案例1。 ．

例2。 ． 很明显, 如果 ．因为奇怪的是, ，我们只需要考虑这种情况 ．如果 ，然后 因此,我们有如果奇怪的是, ．

引理10。如果甚至和 ，然后 ．

证明。如果 ，然后根据引理8．现在,假设 ．的必然结果2， 如果是偶数。因此, 很明显, 如果 ．因为甚至和 ，我们只需要考虑这种情况 ．如果 ，由引理6,我们有或 ．
如果和 ，然后 如果 ，然后 因此,我们有如果甚至和 ．
从推论3.,引理9,引理10,我们有

定理1。 ．
根据引理3.和定理1，我们可以得出结论，我们的启发式是这个问题的最佳可能的多项式启发式。

4.结论

摘要研究了具有最小化最大完工时间的两台相同并行机器的协同调度问题，该问题可以看作是一个包含两个完全相同的并行机器和一般尺寸的工件的IPODS模型。我们首先证明了这个问题是np困难的，然后给出了一个多项式启发式的问题。我们还证明了，除非P = NP，否则不可能有最坏情况性能比界小于2的多项式启发式算法;此外，我们的启发式在最坏情况下的性能比有2的界，这意味着我们的启发式是可能的最好的。在未来的研究中，预计将研究涉及两辆以上车辆或机器的模型。

数据可用性

用于支持这项研究结果的数据包括在文章中。

的利益冲突

作者声明他们没有利益冲突。

致谢

国家教委科学基金项目(no . 18YJC630041);天津市教委科研项目(no . 2019SK069)。关键词:岩石力学，蠕变，蠕变强度，蠕变强度

参考文献

1. Z.-L。集成生产和出库配送调度:回顾和扩展，"运筹学，第58卷，第2期1，页130-148,2010。视图:出版商的网站|谷歌学术搜索
2. I. Averbakh，“有能力交付的在线集成生产-分配调度问题”，欧洲运筹学研究杂志，第200卷，第2期2, pp. 377-384, 2010。视图:出版商的网站|谷歌学术搜索
3. N. G. Hall和C. N. Potts，《调度和批量交付的协调》，运筹学研究年鉴，第135卷，第2期1，页41-64,2005。视图:出版商的网站|谷歌学术搜索
4. Z.-L。Chen和G. L. Vairaktarakis，“生产和分销业务的综合调度，”管理科学第51卷第1期4, 2005。视图:出版商的网站|谷歌学术搜索
5. C. A.乌尔里希，“有时间窗的综合机器调度和车辆路线”，欧洲运筹学研究杂志号，第227卷。1, pp. 152-165, 2013。视图:出版商的网站|谷歌学术搜索
6. 王旭东，“具有可用性约束的机器调度与作业交付协调”，海军研究物流第54卷第5期1，页11-20,2007。视图:出版商的网站|谷歌学术搜索
7. j .学术界。锅和c。Su，“具有作业交付协调和可用性约束的两个并行机器问题”，运筹学研究年鉴号，第235卷。1, pp. 653-664, 2015。视图:出版商的网站|谷歌学术搜索
8. 加里先生和约翰逊先生，计算机和棘手性:np完备性理论指南1979年，美国加州旧金山，弗里曼。
9. 研究。Chang和彭译葶。李，"机器调度与工作交付协调"欧洲运筹学研究杂志第158卷第1期2，页470 - 487,2004。视图:出版商的网站|谷歌学术搜索
10. 何颖，钟伟，顾慧，“基于改进算法的两种单机调度问题”，理论计算机科学，第363卷，第2期。3，页257-265,2006。视图:出版商的网站|谷歌学术搜索
11. 钟伟，国家自然科学基金面上项目，“基于作业交付协调的机器调度问题研究”，欧洲运筹学研究杂志号，第182卷。3, pp. 1057-1072, 2007。视图:出版商的网站|谷歌学术搜索
12. c。苏,j .学术界。锅,t·s·艾。“一种新的启发式算法求解带作业交付协调的机器调度问题”，理论计算机科学第410卷27-29, pp. 2581-2591, 2009。视图:出版商的网站|谷歌学术搜索
13. Z.-L。Chen和G. Pundoor，《综合订单调度和包装》，生产经营管理第18卷第2期6，第672-692页，2009。视图:出版商的网站|谷歌学术搜索
14. 谭俊，“基于单机作业协调的调度策略”，《计算机工程》，优化信，第12卷，第2期2, pp. 265-272, 2018。视图:出版商的网站|谷歌学术搜索
15. G. Dósa, R. Li, X. Han, Z. Tuza， "首次拟合减少装箱的紧绝对界:FFD(l)≤11/9OPT (l) + 6/9。”理论计算机科学， vol. 510, pp. 13-61, 2013。视图:出版商的网站|谷歌学术搜索
16. D.辛奇-列维，《装箱问题的最坏情况新结果》海军研究物流号，第41卷。4，第579-585页，1994。视图:出版商的网站|谷歌学术搜索

版权

版权所有©2020曹丽思等。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。