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

摘要

我们考虑一个调度问题，其中一组作业首先在一个不可用的时间间隔的机器上处理，然后直接交付给客户。我们专注于生产和分销的综合计划，以优化最大交付时间和总交付成本之和。我们在生产部分研究了两类加工机械。在第一类串行批处理机器中，批处理时间是其作业处理时间的总和。在第二类并行批处理机中，批的处理时间是批中包含的作业的最大处理时间。机器具有固定容量，在一批作业的总大小不能超过机器容量的条件下，批量处理作业。如果作业被机器上的不可用间隔中断，则考虑两种作业处理模式，即可恢复和不可恢复。在配送部分，有足够的固定容量的车辆交付完成的作业。一次交付中完成作业的总大小不能超过车辆容量。我们证明了这四个问题在强意义上是NP难的，在这个意义上，作业具有相同的处理时间和任意大小，并且我们提出了一个近似算法来解决这四个问题。此外，我们还证明了该算法在串行批处理机器设置下的性能比为2，在并行批处理机器设置下的误差范围为71/99。我们还通过计算结果评估了近似算法的性能。

1.导言

在现实的供应链环境中，生产和分销的联合考虑有助于制造商做出更高层次的决策，因此许多研究人员一直在研究此类集成调度问题的各种模型[1可能是第一个考虑工作交付时间安排的研究人员。霍尔和波茨[2]研究了涉及供应商、制造商和客户的集成调度。到目前为止，有越来越多的文献和各种各样的新模型研究作业交付的调度问题。对于一台机器，Chen和Vairaktarakis[3.]研究了最大交货时间和总运输成本的加权和具有相对偏好的最小化问题，该问题使用了足够的不受容量限制的车辆将已完成的工作交付给客户。他们针对一个客户和多个客户提出了两种最优算法。陈(4Wang等人[5研究了生产与配送作业的综合调度问题。

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

当并行分批机上加工，多个作业可以同时在计算机上在同一时间，使得一批的处理时间是包含在批作业的最大处理时间处理为批量。有界并行分批加工机设置由Lee等人介绍。[13]，这在半导体工业的磨合操作和金属加工工业的热处理操作中经常遇到[14]证明了该问题是一个NP难问题，并给出了一些近似算法。和Brucker等人[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]考虑用机器的可用性约束，取决于位置的处理时间，和时间依赖性的建立时间的单机器序列分批调度问题。范等人。[24研究了具有不可用区间的单有界并行批机器上对客户最大交货时间最小化的综合调度问题。摘要针对具有相同加工时间和相同加工时间和相同加工规模的工件，研究了最坏情况比为3/2和5/3的两种近似算法。

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

2.问题公式化

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

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

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

3.四个问题的性质

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

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

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

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

4.算法和分析

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

4.1.算法H

步骤1：将所有作业重新索引为 这 ．步骤2:使用First Fit decrease (FFD)规则将作业分批分配，在分批中作业将在机器上一起处理。构建第一个空批处理如果批次的当前总大小只不过是U。当所有作业都被检查并且仍然需要分配作业时，构建第二批并分配剩余的作业如步骤1，重复分配的顺序，直到没有剩下的工作。令X是在步骤2中生产的批次的数目。步骤3：将批次按其处理时间的非递减顺序分配给从时间0开始连续处理的批次，不可用间隔除外。第4步：让。 和 交付第一个完成的批次的 ．同时,提供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）、上海理工大学重点学科“应用数学”（XKKP Y1604）的支持，该课题是“一级研究生教育领导计划”的子课题。上海理工大学资源回收科学与工程研究中心、上海环境科学与工程（资源回收科学与工程）高远学科。

工具书类

1. C. N.波茨，“一组机用测序的发布日期和交货时间启发式的技术说明分析，”行动调查，第28卷，第6期，第1436-14411980页。查看在：出版商的网站|谷歌学者
2. N. G. Hall和C. N. Potts，《供应链调度:批量和交付》，行动调查第51卷第1期4，页566 - 584,2003。查看在：出版商的网站|谷歌学者
3. Z.-L。Chen和G. L. Vairaktarakis，“生产和分销业务的综合调度，”管理科学，第51卷，第4期，第614-628页，2005年。查看在：出版商的网站|谷歌学者
4. Z.-L。集成生产和出库配送调度:回顾和扩展，"行动调查，第58卷，第2期1，第130-148，2010。查看在：出版商的网站|谷歌学者
5. D. Y.王，澳Grunder和A. E. Moudni，“生产和分销业务的综合调度：回顾”工业与系统工程国际期刊，卷。19，没有。1，第94-122，2015年。查看在：出版商的网站|谷歌学者
6. H. S. Mirsanei, B. Karimi，和F. Jolai，“具有两批处理机器和不同作业尺寸的流水车间调度”，国际先进制造技术杂志，卷。45，不。5-6，第553-572，2009。查看在：出版商的网站|谷歌学者
7. 李文昌，吴昌昌，徐鹏辉，“带有释放时间的单机学习影响调度问题”，ω，第38卷，第1期，第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，“在串行批处理机器上集成生产和交付调度，以最小化完工时间，”理论计算机科学， vol. 572, pp. 50-57, 2015。查看在：出版商的网站|谷歌学者
13. 彭译葶。李，R. Uzsoy，和L. A. Martin-Vega，“半导体老化操作调度的有效算法”，行动调查，第40卷，第4期，第764-775页，1992年。查看在：出版商的网站|谷歌学者
14. R. Uzsoy，“用不相同的作业大小调度单批处理机”，国际生产研究杂志，第32卷，第2期7、1994年。查看在：出版商的网站|谷歌学者
15. P. Brucker, a . Gladky, H. Hoogeveen等人，“调度分批机”，杂志的调度，卷。1，不。1，第31-54，1998年。查看在：出版商的网站|谷歌学者
16. Y. H. Lee和Y. H. Lee，“最小化最大完工时间启发式方法用于调度具有不同作业大小的单个批处理机，”国际生产研究杂志，第51卷，第12期，第3488-3500页，2013年。查看在：谷歌学者
17. 李思生，袁军，范斌，“基于家庭作业的无界并行批量调度与配送协调”，信息处理信函号，第111卷12，页575-582,2011。查看在：出版商的网站|谷歌学者
18. 龚辉，陈德华，徐科，“具有等待时间约束的并行批量调度与运输协调”，科学世界日报文章编号356364,8页，2014。查看在：出版商的网站|谷歌学者
19. L. Lu和J.元“与工作交付无界批量并行调度极小化”运筹学快报第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. 马云、朱春春和左春春，“具有确定性机器可用性约束的调度调查，”计算机与工业工程，第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期，第351-358页，2014年。查看在：出版商的网站|谷歌学者
27. j.m. Valério，“使用列生成和分支绑定的装箱问题的精确解决方案，”运筹学纪事，第86卷，第629-6591999页。查看在：谷歌学者

版权

版权所有©2020京帆。这是一篇发布在知识共享署名许可协议如果正确引用了原始工作，则允许在任何媒体中的不受限制使用，分发和再现。