具有不可用约束的单个有界批处理机集成调度问题

抽象的

我们考虑一个调度问题，其中一组作业首先在具有不可用间隔的计算机上处​​理，然后直接向客户发送到客户。我们专注于综合生产和分配计划，以便优化最大交货时间和总递送成本的总和。我们研究了生产部件中的两类加工机器。在第一类中，串口机器，批处理的处理时间是其作业的处理时间的总和。在第二类，并行批处理机中，批处理的处理时间是批处理中包含的作业的最大处理时间。机器具有固定容量，并且在批次中作业的总大小不能超过机器容量的条件下，在批处理中处理作业。如果通过机器上的不可用间隔中断，则考虑两种作业处理模式，即恢复和不可恢复的模式。在分销部分中，有足够的车辆具有固定的能力来提供完成的作业。完成工作中已完成的工作的总规模不能超过车辆容量。我们表明，这四个问题是在工作中具有相同处理时间和任意尺寸的强烈意义上的NP - 困难，我们提出了一种解决这四个问题的近似算法。 Moreover, we show that the performance ratio of the algorithm is 2 for the serial-batch machine setting, and the error bound is 71/99 for the parallel-batch machine setting. We also evaluate the performance of the approximation algorithm by the computational results.

1.介绍

对生产和分配的联合审议对于制造商家在现实供应链环境中为制造商提供更高的级别决定，这些研究人员在研究这些综合调度问题的各种模型上进行了研究。Potts [1可能是第一个考虑工作交付时间安排的研究人员。霍尔和波茨[2]学习综合调度，涉及供应商，制造商和客户。到目前为止，文学数量越来越多地和各种新模型正在调度工作交付问题。一体机，陈和vairaktarakis [3.]研究了最大交货时间和总运输成本的加权和具有相对偏好的最小化问题，该问题使用了足够的不受容量限制的车辆将已完成的工作交付给客户。他们针对一个客户和多个客户提出了两种最优算法。陈(4Wang等人[5研究了生产与配送作业的综合调度问题。

在大多数带交付的调度模型中，一台机器一次处理一个任务。然而，一种新的与批处理相关的集成调度问题已经被许多研究者所研究。批量调度是由许多工业生产过程驱动的。例如，在半导体制造的老化阶段，老化炉可以同时处理多个工作。批量处理机一般有两种版本:串行批和并行批，根据[6］．在串行批处理机上处理作业时，可以对作业进行批处理，一次处理一批中的一个作业，这样，一批作业的处理时间就是该批作业的处理时间之和。作业的学习效应往往伴随着序列批量调度问题。李等人[7和Pei等人[8- - - - - -10研究了作业恶化或学习影响下的最大完工时间最小化的系列批量调度问题。在[中没有设置时间7]但是[8- - - - - -10］．Pei等[11研究了具有恶化作业的生产与运输的协调调度问题。包括已完成的工作在内的批次将由一辆车辆交付给客户，在一次交付中只有一批。他们分析了一些有用的性质，给出了一般情况下的启发式算法和特殊情况下的两种最优算法。卢等人[12[摘要]研究了以最小化最大完工时间为目标的串行批量机器上的生产与交货一体化调度问题，并从作业的生产与交货是否允许分割的角度考虑了四个不同的问题。

在并行批处理机上进行处理时，可以同时在一台机器上以批的形式对多个作业进行处理，使一个批的处理时间为该批所包含作业的最大处理时间。Lee等人引入了有界并行批处理机设置[13]，在金属加工行业中的半导体工业和热处理运营中，总是遇到的燃烧运营。Uzsoy [14]显示问题是NP - 难以最大限度地减少单个有界并行批量机上的MakEspan，并提供了一些近似算法。和布鲁克等人。[15讨论了两种变体:无界模型和有界模型。李和李[16]提出了一种通过迭代分解混合整数规划模型的启发式算法。李等人[17]，龚等人。[18]陆和元[19， Cheng等[20.研究了并行批处理机器上的生产与分配的综合调度问题。在[20.]，作者着重于找出工作的时间表和交货计划，以使最大的交货时间最小化。他们证明这个问题可以用最优方法解决O（n日志n，并提出了两种近似算法，在处理时间相同的情况下性能比为11/9，在任意处理时间和任意大小的情况下性能比为2。

到目前为止，大多数的工作都是对机床设置进行研究，而这些设置总是可用的。但是，在生产过程中，由于故障的发生或维修的需要，机器可能会出现不可用的情况，这称为机器不可用约束下的调度。当作业处理因机器不可用而中断时，一旦机器恢复可用，中断的作业可能是可恢复的，也可能是不可恢复的。在可恢复的情况下，中断的作业可以继续处理，而在不可恢复的情况下，中断的作业需要重新处理。针对最大交货期最小化的有能力车辆集成调度问题，Wang, Cheng [21，提出了3/2近似算法，并给出了最坏情况比为3/2的实例。关于这一研究流的更多细节可以在Wang等人的工作中找到[5和Ma等人[22］．关于具有不可用约束的批处理机的集成调度问题，已有一些文献进行了研究。Pei等[23研究了具有机器可用性约束、位置依赖的加工时间和时间依赖的安装时间的单机串行批量调度问题。Fan等[24研究了具有不可用区间的单有界并行批机器上对客户最大交货时间最小化的综合调度问题。摘要针对具有相同加工时间和相同加工时间和相同加工规模的工件，研究了最坏情况比为3/2和5/3的两种近似算法。

本文研究了一个有界批量机器上的客户集成调度问题，该问题中工件具有相同的加工时间，并且有足够的车辆将已完成的工件交付给客户。目标是将最后一个完成的工作交付给客户时的交付时间和总交付成本的总和最小化。在不可用期后的中断作业处理过程中，根据不同的情况和机器类型，可分为四类问题，即串批问题和并行批问题。在实际的制铝过程中，连续配料是常见的。圆筒形铝锭在同一批次的挤压机上依次进行加工，并有一个检查时间表。此外，在半导体制造的老化阶段，老化炉可以同时处理多个工作，这是平行批处理的形式。作为计划，烤箱必须停止接受检查。所有完成的工作必须尽快送到客户手中。因此，在如此复杂的环境下，如何有效地安排生产和交货是值得研究的问题。

2.问题公式化

一组工作 给予，工作有处理时间和尺寸 ．每个作业有任意大小，但处理时间相同 为 ．在生产部分中，机器具有容量 ，也就是说，如果作业的总大小不超过机器的容量，它可以同时处理多个作业。我们讨论了两种类型的批，即串行批和并行批。对于串行批处理，批处理时间为其作业的处理时间之和。对于并行批处理，批处理时间为批处理中所包含作业的最大处理时间。同时，机器有一个不可用期 因为维修和故障。让为不可用期的长度，即: ．如果一批作业中至少有一个作业被不可用时间段中断 ，中断的作业可能在之后继续处理 ，在这种情况下，我们称其为可恢复的，用r−一个，或者需要重新处理 ，定义为不可恢复的，表示为nr−一个．在后一种情况下，包含该作业的批处理时间不受并行批处理的影响以及该作业的总加工时间和该系列配料机的机器闲置时间。在交付部分，有足够的车辆将已完成的工作交付给客户，每辆车都有相同的能力 ．相似 [20.，我们假设 ，在哪里x≥2和x为正整数。机器与客户之间的一次运输价格用总配送成本表示为 ．让是送货时间 ，即，包含作业的批的到达时间给客户。让是所有工作中最长的交货时间。我们的目标是最小化最大交付时间和总交付成本的总和。使用Chen提出的五域表示法[4为表示一个综合调度问题，本文将该问题的四类表示为:

在这里,h₁表示一个不可用的间隔和V（∞，c)显示车辆的情况。另外，因为只有一个客户，所以车辆应该直接从制造商把作业运送到客户那里。在的问题和 ，s-batch意味着串行批次。相反，在问题和 ， 批处理意味着并行批。

我们将论文的其余部分组织如下。节3.，我们展示所有问题都在强烈的意义上努力，提出了一些基本的性质。节4，给出了这四个问题的近似算法，并证明了这四个问题的不同误差界。最后对研究结果进行了总结，并对未来的研究方向进行了讨论。

3.四个问题的属性

在本节中，我们分析了问题的计算复杂性- - - - - -．

定理1。问题- - - - - -都是强烈的NP-hard。

证明。考虑特殊情况的问题和 ，在这 ， ，和c= 0，即每个作业的加工时间为0，机器上没有不可用间隔，没有交货问题 ．因此,这个问题等价于最小化批数，即装箱问题，这是一个众所周知的强np困难问题。因此,问题和是强np困难。
类似地，我们构造特殊情况的问题和 ，在这 和c=0. Since each job has a processing time of ，每一批都有一个处理时间 ．因此,这个问题也等价于装箱问题。因此,问题和都是强烈的np困难。
结合装箱问题，研究了这四个问题的最优解的一些性质。

引理1。存在最佳的时间表问题的为 ，满足下列性质:（1）让为最优调度中的批数 ；然后， (2）批次在不可用期前后进行连续处理（3）早期可用的批处理早期交付（4)第一批交货包括分批，每一批都是最后一批交付x批次,和两个正整数满足吗 和 这种引理可以证明它类似于[21］．

4.算法和分析

为了使目标函数值最小，必须在每批分配足够多的作业，以减少批数和交货量。因此，结合装箱问题的算法，我们提出以下算法来解决四个调度问题。

4.1。算法H.

第1步：reindex所有工作 这 ．步骤2：使用第一个拟合减少（FFD）规则将作业分配成批次，其中将在机器上处理作业。建立第一个空批处理如果当前批次的总尺寸，则在步骤1中的序列中逐个将作业置入其中只不过是U。当所有作业都被检查并且仍然需要分配作业时，构建第二批并按步骤1中的顺序分配其余作业。重复分配任务直到没有工作剩下。设X为步骤2生产的批次数。步骤3：将其处理时间的非分解顺序分配批处理，以便在除了不可用间隔之外的时间0连续处理。第四步:让。 和 交付第一个完成批次的 ．同时,提供x批次立即在以下每一个交付。当最后一个x批次将批量交付给客户，算法完成。

回顾装箱问题的FFD规则，我们可以很容易地得到引理2．

雷玛2。(见[25])。 ．
根据引理2，我们可以探讨相应的值和如果 (见表1)．
为了列出之间的值相应的关系和如果 ，我们用两个正整数 和 这样 类似于在[26］．因此，我们可以得到Table2．
进一步分析了算法H产生的目标函数值与问题中最优调度的关系- - - - - -,分别。为了方便，我们使用表示通过算法H获得的时间表。 ．

引理3。（1） ，在哪里机器上的空闲时间在计划中的不可用间隔之前吗 ， 的问题 ，分别(2） ，在哪里机器上的空闲时间在计划中的不可用间隔之前吗 ， 的问题 ，分别

证明。（1）根据算法H的步骤3，批次按照其处理时间的非递减顺序进行处理。让 ， 在开始时间之前完成的工作数量 日程安排 ， ，分别。因为之前的可用时间长度在机器上是固定的，我们有 ．因此, ．(2）因为每个批处理的处理时间等于无论其中有多少个作业，并且通过算法H处理的开始时间为零，很明显，在不能再多了吧 ，也就是说, ．对于问题 ，我们使用 ， ， ,为表示最大交货时间，总交货成本为 ，和（ )，分别。我们可以很容易地得出 ， ， ，和为 ．

引理4。（1）在这个问题 ， 和 (2）在这个问题 ， 和 （3）在这个问题 ， 和 ， （4)在这个问题 ， 和

证明。因为批量的过程在问题中是可恢复的 ，算法H的结果与最优解的区别仅仅是交付的次数。在这个问题 ，算法H的结果与最优解之间的机器空闲时间也不同。而且，在这个问题上 ，总处理时间在算法H的解决方案中需要，但是在最佳解决方案中需要。此外，机器的空闲时间的差异在算法H的目标函数值中是显而易见的，并且问题中的最佳时间表 ．
值得注意的是，最后批处理的完成时间大于最佳计划中的不可用间隔的结束时间（ )．否则，性能比将趋于无穷大。
从每一个问题的目标中，我们发现两者之间的关系和是至关重要的。因此，我们探讨以下引理。

引理5。(见[24])。 ．

证明。 是显而易见的。由于x≥2,引理2的解释 ， ，我们可以推断出 此外,如果 ，我们有 这与引理2．
因此，我们可以轻松获得相应的值和如果 (见表3.)．
为了简化每个问题的目标函数值，我们使用和分别表示算法H和最优调度得到的目标函数值。

定理2。算法H是求解该问题的2-近似算法( ）问题( )，最坏情况的比率很紧。

证明。根据雷姆玛4，很明显 从表3.时，算法达到最坏情况比 和 ．
对于这个问题( )，因为 （1在引理3.,我们有 同样的,当 和 ，算法达到了最坏情况比。
考虑以下实例:n= 6,= 2,U= 7,x= 2, ，和 ， ．算法H产生的时间表如下：第一次交付包括作业因为第一批在时间2交付;第二次发货包括两个批次，其中包括作业和和工作 ， ，和分别按时间交付 ．因此, ．然而，在最优调度中，只有一个交付，包括两个由作业组成的批次 ， ，和和工作 ， ，和分别。此交货时间发生 ，最优目标值为 ．如果是否足够大，我们有吗 ．
对于这个问题( ）问题( )，则得到算法H的误差界。

定理3。算法H在解决问题时的误差范围为71/99 ( ）问题( )．

证明。因为(2)的引理3.,我们有 我们只需要分析的上界 ．并根据两种情况对结果进行了证明 和 ，分别。案例1: ．我们用两个子案例来讨论这种情况。子箱1.1：当我们考虑这种情况时 ，我们可以得到下面的不等式 （ ）根据表3.： 为 ， 根据表1和2．为 ， ，我们有 ．子情形1.2:当我们考虑 ，我们从表中得到如下不等式3.除了 ： 此外,与 ，我们有当k = 0时，k = 1= 4，很容易推断不等式（7)时, ．为 ， ．而且，我们有 根据表1和2．因此, ．案例2: ．我们可以轻松获得不平等（10)．因为 根据表2和 根据引理5,我们获得 和 和 ．

5.计算结果

由于这四个问题都是强NP-hard问题，且装箱问题又包含在这些问题中，因此解决这些问题的成本高，耗时长。但是，为了评估算法H的有效性，我们考虑了四个小尺寸问题的数值模拟。针对[中的装箱问题，采用分枝定界算法对批次进行处理，得到最优调度。27]及交付为(4在引理1．

用vc++编写了近似算法和分支定界算法，并在微机上进行了计算实验。我们使用三个不同的工作数字，n= 30和50。设每个作业的处理时间为1，所有作业的大小随机产生于离散均匀分布[1，10］．让机器的容量U= 3,7和车辆的容量V=徐= 2U, 10U．我们设置了两个不可用时期长度的两个级别 和两层的起始时间的不可用间隔 在实验中。每个递送批量的成本设定为 对于每个组合n， ， ，和 ，随机使用20个实例，计算结果汇总于表中4来7，报告每个参数组合的最优解和算法H解的平均CPU时间秒数。算法H产生的解的误差百分比计算为 ．

从表中可以看出4- - - - - -7当任务数量增加时，算法H的平均CPU时间以多项式倍增加，而对于分支定界算法，则以指数倍增加。的最优解的平均最坏情况误差界 ）和( ）一般多于( ）和( ）因为不可恢复的条件。最后，最重要的是，这四个表表明了近似算法的有效性，四个问题的实际误差界限低于理论误差界限。

6.结论

我们考虑四个综合调度问题的总和最小化最大的交货时间和交货总成本,其中一组的工作是首先在单个批处理机器的不可用时间间隔,然后直接交付给客户,工作有相同的处理时间和任意大小。我们证明了这四个问题都是强np困难的，并提出了它们的近似算法。同时，我们得到了该算法对串行批量机器设置和并行批量机器设置的最坏情况误差界。我们还提供了计算结果来评估启发式的性能。

未来的研究方向可能会集中在其他工作和车辆的设置上，如任意加工时间和任意尺寸的工作或一辆容量有限的车辆。

数据可用性

用于支持本研究的随机数据可根据要求从通讯作者处获得。

利益冲突

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

致谢

本研究得到了中国国家自然科学基金（116013 16），上海理工大学（XXKP Y1604），“一流研究生教育领导计划”的重点学科“应用数学”，资源回收研究中心上海理工大学上海市环境科学与工程（资源回收科学与工程）科学与工程学科。

参考

1. C. N. Potts，“技术笔记——对带有发布日期和交货时间的一台机器排序的启发式分析，”运筹学，卷。28，不。6，PP。1436-1441,980。视图:出版商的网站|谷歌学者
2. N. G. Hall和C. N. Potts，《供应链调度:批量和交付》，运筹学第51卷第1期4，页566 - 584,2003。视图:出版商的网站|谷歌学者
3. Z.-L。Chen和G. L. Vairaktarakis，“生产和分销业务的综合调度，”管理科学第51卷第1期4，pp。614-628,2005。视图:出版商的网站|谷歌学者
4. Z.-L。集成生产和出库配送调度:回顾和扩展，"运筹学，第58卷，第2期1，页130-148,2010。视图:出版商的网站|谷歌学者
5. 王德元、葛瑞德、穆德尼，“生产与分销业务的综合调度:述评”，工业与系统工程国际期刊第19卷第2期1, pp. 94-122, 2015。视图:出版商的网站|谷歌学者
6. H. S. Mirsanei, B. Karimi，和F. Jolai，“具有两批处理机器和不同作业尺寸的流水车间调度”，国际先进制造技术杂志第45卷第5期5-6，页553-572,2009。视图:出版商的网站|谷歌学者
7. 李文昌，吴昌昌，徐鹏辉，“带有释放时间的单机学习影响调度问题”，ω，卷。38，不。1，pp。3-11，2010。视图:出版商的网站|谷歌学者
8. 裴建军，刘旭东，范伟，杨士生，“具有独立设置时间和退化作业处理时间的单机串行批量调度，”优化信，第9卷，第5期。1, pp. 91-104, 2015。视图:出版商的网站|谷歌学者
9. 刘学军，P. M. Pardalos, a . Migdalas，和S. Yang，“具有时间依赖性设置时间和退化和学习影响的单机器串行批量调度，”全局优化学报，第67卷，第5期1, pp. 251-262, 2017。视图:出版商的网站|谷歌学者
10. 裴建平，刘旭东，P. M. Pardalos et al.，“基于多作业类型和顺序相关的安装时间的单串行批处理机的作业调度，”运筹学研究年鉴，第249卷，第2期。1, pp. 175-195, 2017。视图:出版商的网站|谷歌学者
11. 刘旭东，范伟，杨树生，“基于最小完工时间的两阶段供应链中退化作业的批量调度，”欧洲运筹学研究杂志，第244卷。1, pp. 13-25, 2015。视图:出版商的网站|谷歌学者
12. L.Lu，L. Zhang和L. WAN，“串行批量机上的综合生产和交付调度，以最大限度地减少MEPESPAN”理论计算机科学， vol. 572, pp. 50-57, 2015。视图:出版商的网站|谷歌学者
13. 彭译葶。李，R. Uzsoy，和L. A. Martin-Vega，“半导体老化操作调度的有效算法”，运筹学，卷。40，不。4，PP。764-775,1992。视图:出版商的网站|谷歌学者
14. R. Uzsoy，“用不相同的作业大小调度单批处理机”，国际生产研究，第32卷，第2期7、1994年。视图:出版商的网站|谷歌学者
15. P. Brucker, a . Gladky, H. Hoogeveen等人，“调度分批机”，杂志的调度， vol. 1, no. 11，第31-54页，1998。视图:出版商的网站|谷歌学者
16. Y. H. Lee和Y. H. Lee，“最小化最大完工时间启发式方法用于调度具有不同作业大小的单个批处理机，”国际生产研究第51卷第1期12，pp。3488-3500,2013。视图:谷歌学者
17. 李思生，袁军，范斌，“基于家庭作业的无界并行批量调度与配送协调”，信息处理字母号，第111卷12，页575-582,2011。视图:出版商的网站|谷歌学者
18. 龚辉，陈德华，徐科，“具有等待时间约束的并行批量调度与运输协调”，科学世界杂志文章编号356364,8页，2014。视图:出版商的网站|谷歌学者
19. “基于最大完工时间最小化的无界并行批量调度”，行动研究快报第36卷第2期4，页477 - 480,2008。视图:出版商的网站|谷歌学者
20. B.-Y。程,j . Y.-T。梁国梁，李国强，李淑莲。“单批机器调度与交货，”杨，海军研究物流（NRL）第62期6, pp. 470-482, 2015。视图:出版商的网站|谷歌学者
21. 王旭东，“具有可用性约束的机器调度与作业交付协调”，海军研究物流第54卷第5期1，页11-20,2007。视图:出版商的网站|谷歌学者
22. Y. Ma，C. Chu和C. Zuo，“通过确定性机器可用性约束调度调查”计算机与工业工程，第58卷，第2期2，页199-211,2010。视图:出版商的网站|谷歌学者
23. 裴建平，刘旭东，P. M. Pardalos, K. Li, W. Fan, a . Migdalas，“具有机器可用性约束、位置依赖的加工时间和时间依赖的设置时间的单机串行批量调度”，优化信，第11卷，第5期。7, pp. 1257-1271, 2017。视图:出版商的网站|谷歌学者
24. 范建军，吴昌堂，郑廷恩等，“具有不可用约束和作业交付的单有界并行批处理机器调度”，《自动化学报》，第3期信息和管理中的算法方面柏林，德国，2020。视图:谷歌学者
25. 裴建军，程斌，刘旭东，P. M. Pardalos，孔明，“基于位置学习效应和线性设置时间的单机和并联串行批量调度问题”，运筹学研究年鉴第272期1，页217-241,2019。视图:出版商的网站|谷歌学者
26. G. Dosa, Z. Tan, Z. Tuza, Y. Yan, and C. S. Lányi，“具有不同作业大小的批量调度的改进边界”，海军研究物流（NRL），卷。61，没有。5，pp。351-358,2014。视图:出版商的网站|谷歌学者
27. j.m. Valério，“使用列生成和分支绑定的装箱问题的精确解决方案，”运筹学研究年鉴，卷。86，pp。629-659,1999。视图:谷歌学者

版权

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