具有机器相关设置时间的双机流水车间批量调度

摘要

研究了一个双机流水车间的批量调度问题。我们假设单位处理时间作业、批处理可用性和机器相关的设置时间。目标是找到一个作业分配到整数大小的批次和一个最小化完工时间的批调度。我们介绍了这个问题的一个非常有效的封闭解。

1.介绍

最近的调查论文《带安装时间和成本的调度问题的调查》[1[将批量调度问题分类为具有批处理和非匹配注意事项的人，具有序列无关和序列依赖的设置时间，并根据机器环境和目标函数。该调查包含大约300个参考文献，清楚地表明了本主题的重要性和相关性。

在本文中，我们在2机流量上研究批量调度问题。目标函数是最低的mapspan。研究的模型中的潜在假设如下。

(我)批可用性:当批处理的最后一个作业完成时，所有的作业都完成了(然后整个批处理可以在第二台机器上处理，或者交付给客户)。(2)Nonanticipatory设置：在完成第一台机器上的批处理后，可以仅执行第二台机器上的设置。（iii）批量一致:批处理在两台机器上是相同的。(iv)计算机有关的设置时间：机器1和机器2具有不同的设置时间（所有批次相同）。

Cheng等人在上述假设下证明了2-machine flow-shop具有强NP-hard特性[2]和玻璃等人。[3.］．然而，我们专注于一个重要的特殊情况，这被证明具有优雅的封闭形式解决方案。具体来说，我们假设单位处理时间作业．众所周知，这种设置有各种各样的应用，例如在制造环境中，它反映了生产相同产品序列的通用系统。单元作业调度在许多调度环境中得到了广泛的研究。Mosheiov和Oron研究了具有单位加工时间作业的流水车间的批调度问题[4.那5.， Ng和Kovalyov [6.]和mosheiov等人。[7.］．

在所有上述文件中，作者认为相同（即，机器无关）的设置时间。如上所述，我们的研究侧重于计算机有关设置。包含机器相关设置的调度问题存在于许多实际应用中，并在各种环境中得到了广泛的研究。然而，本文首次考虑了一个同时假设单位作业和机器依赖设置的模型。当在不同机器上的作业上执行类似或相同的操作，但必须在其中一台机器上执行需要常量时间的额外操作(或在不同的机器上执行不同的常量时间操作)时，这种设置的可能应用程序。这些操作可以被视为批处理操作，其中给定批处理的所有作业都经历某种类型的过程，该过程在恒定的时间内执行，独立于批处理中的作业数量。这些操作可能包括在第一台机器上对到达的批次进行特殊装载或记录，初始质量保证，或在加工前对批次进行特殊准备。最后一台机器上的固定时间操作同样包括为装运和分派批次(冲压、喷漆)准备批次、质量保证程序(对固定数量的物品进行随机测试或批处理程序，如扫描)或行政操作，其中可能包括文书工作、数据记录、等等。

我们区分以下两种（类似但不对称）案例：第一台机器上的设置大于第二台机器上的设置，第一台机器上的设置小于第二台机器上的设置。对于这两种情况，我们证明了最大时间最小化问题是有效的时间,N是工作的数量。值得注意的是，现有算法解决了本文研究的问题的特殊情况，即何时,在时间。因此，即使问题更加复杂，本文提出的算法也减少了获得最优解所需的计算工作量。需要注意的是，现有的算法和当前的求解过程都不是多项式问题的输入大小。因为我们考虑的是单元处理时间作业，所以输入包含三个值()、作业数量以及两台机器上的安装时间。因此，即使程序要求时间是输入大小的指数。然而，我们怀疑是否有办法更有效地表示这一问题的最佳解决办法。

应该注意的是，解决方案的第一步包括解决“放松版本”，其中不需要批量大小的完整性(见下文)。实际上，这是很多流问题，因为它包括把给定的作业分成子块，以便允许它们在流程车间的两台连续机器上重复处理。陈和斯坦纳[8.那9.]，刘[10]解决了具有整数大小批次的流水车间的批量流问题。Vickson [11]处理了带有机器相关设置时间的流水车间的批量流。然而，据我们所知，本文所考虑的模型(假设与机器相关的设置，并要求批量规模的完整性)以前没有研究过。

节2，给出了问题的表示法和公式。最优解见第一部分3.（和附录）。部分4.包含结束语和对未来研究的想法。

2.制定

在时间0时，独立的作业可以在2机流程车间上进行处理。表示工作的处理时间  在机．因此，我们假设单位处理时间为了和一世= 1, 2。调度器的任务是将作业划分成批(即找到它们的最佳数量和大小)，并对这些批进行调度，以使最大完工时间最小化。

在处理新批之前，一个(整数)依赖于机器的设置时间，发生。如上所述，设置被假定为非植物．对于给定的批分配，让表示批数，让表示的大小批。批处理的总处理时间显然等于其大小。我们假设（见上文）batch-availability和批量一致．批处理完成时间，这是批量中包含的所有作业的完成时间．采用传统的三场表示法，本文研究的问题是．

评论1。一个标准的假设是所有的输入参数都是非负整数，这意味着在我们的例子中(相同的)处理时间和(依赖于机器的)设置都是整数。可以假定经过适当的扩展后，所有处理时间都具有单位时间，但显然，设置不一定保持整数。因此，我们允许并研究非整数设置时间的情况;看到评论3.节3.和评论. 1在附录中。(请注意，对于这种更一般的情况，计算工作量仍然存在通过使用所提出的算法。）

3.的一个封闭形式的解

我们在这里关注的是在第一台机器上的设置时间更短的情况(例虽然没有完全对称，但它是类似的，其分析出现在附录中。机器独立设置的情况，即，何时研究过[4.那6.]。)为了方便，我们先解轻松问题的版本(由)，其中批大小允许有非整数值。

首先，我们引入给定批数的最优最大完工时间的下界，K.．如在经典的2机器流店问题中，当在第二台机器上的连续批次之间产生空闲时间时，获得下限。在第二台机器上处理第一批次之前，我们获得了不可避免的空闲时间，我们获得

达到这个下界的调度必须不包含第二台机器上连续作业之间的空闲时间。无空闲时间的充要条件如下:这是真的，因为完成批处理的时间在第一台机器上不能超过批处理的完成时间在第二台机器上一个满足这些条件的计划包括由下列一组获得的批规模平等：所得到的进度包括以下增加批量大小的顺序:．考虑到，我们很容易获得

上述时间表具有比较下限的Mapspan值，因此对于问题而言是最佳的和一个给定的K.价值。

上述调度的makespan值为

请注意,(3．3）是一个严格凸起的功能K.  and the unique minimum is given by

回想一下,K.表示最佳（整数）批次数，因此，由于凸起（3．3）

两个都和应该考虑。

我们得到了问题松弛版本的最优解()由(3．4），（3．5）， 和 （3．2)．

我们现在考虑原始问题，其中批大小被限制为整数，表示为．最佳解决方案的下限是

(注意上述定义是松弛版的第一批解的大小。在特殊情况下是整数，那么，显然，“天花板”是冗余的，下限与所给出的mapespan值相同（3．3)．）

下界在(3.6)为大于或等于问题最大完工时间值的最小整数．任何由批次组成的计划整数的大小产生这个最大完工时间显然是最优的。

如果(给出(3．2）是整数，然后清楚地，所有批次都是整数和问题的解决方案是原问题的最优解，．对于一般情况，在哪里是不是一定是整数，让．

自从，我们得到是整数(严格小于K.)．基于问题的解决方案，我们构建问题的解决方案通过四舍五入批量和四舍五入大小的剩余批次,．一种选择是四舍五入计算第一个的大小分批，最后一个的尺寸四舍五入L.批次。最终分配给批的作业是不难证实，在上述时间表中:机器2上批次1之前的空闲时间为和机器2上连续批次之间没有空闲时间。因此，该调度的最大完工时间值为

请注意，MakEspan的上述值与问题的下限相同在(3.6)．我们得出结论，任何价值，上述时间表为最佳。

评论2。值得一提的是，最佳解决方案不是唯一的，其他舍入程序可能导致其他最佳时间表。一个替代的例子包括舍入第一L.批次和最后一个舍入批次。
最终分配给批的作业是．
在这种情况下，很容易证实机器2上连续批次之间没有空闲时间那批次之间存在1个空闲时间和,机器2上连续批次之间没有空闲时间．本附表的Mapespan价值（清楚，鉴于这一点不是整数)是 makespan的这个值与(3．7)，这意味着这个时间表也是最优的。

还需要找到最优的批数，．请注意，由于完整性和， makespan函数(3．7)，可稍作修改如下:

由此可见值最小化(3．7)亦可使(3．9)．因此最佳K.给出的放松版本的价值（3．4） 和 （3．5)对于整数版本是最优的。我们用算法中给出了一个形式化的算法3．1．

算法3.1（Flowshop_makespan_)．输入:步骤1（最佳批次数）。计算和（从 （3．4） 和 （3．5)．
如果((3．7),然后除此以外第2步（最佳批次）。 （从 （3．2)．第3步（舍入）。计算批处理大小的非整数部分，．
计算要四舍五入的批次数量，
批处理的最佳整数分配是

运行时间
很容易验证算法在中时间。虽然在恒定的时间内执行最佳批次数和最佳MapeSpan的计算2算法需要计算批量大小。由于批次的数量是，所需的计算工作量为．步3.能轻松地在里面表演吗时间，因此，总运行时间算法3．1是．

算法的使用3．1在下面的示例中演示。

例3.2。认为,那．在步骤1我们计算和(关联最佳完工时间值为111)。在步骤2我们获得批量尺寸（对于轻松的问题）：,．舍入程序（步骤3.)得到以下最优批大小顺序:和;见图1．作为批次数量的MEPESPAN（用于放松和整数版本的函数）在图中呈现2．

评论3。考虑有趣的概括非整数设置时间。在这种情况下，最佳K.价值（3．7）可能与（3．3），（例如，如果那和我们获得这意味着松弛问题的值是6或7，但是，最优整数版本的值是5。)似乎在这种一般情况下(非整数设置)，一个封闭形式的表达式最优值似乎不存在，必须执行搜索。很明显，我们要搜查所有可能的地方值(1到N）保证最佳解决方案。但是，由于最小的批次，因此有限搜索似乎是足够的必须是负的。从(3．2我们获得．因此,．第一个术语是严格负面的（回想一下），暗示这一点K.值域是整数吗,在那里 我们的结论是，尽管需要考虑批次数量的可能值范围，K.，解决非整数设置时间的问题所需的计算工作．

评论4。不难证明，本节提出的算法是对Mosheiov和Oron [4.]，对于机器独立设置的情况。替代时在沿上述算法的表达式中，我们获得了对该特殊情况的最佳解决方案。特别是替代在步骤2导致“平均分配”批次(使用术语[4.)，以及舍入过程，即舍入第一个的大小批次和舍入剩余的大小批处理生成最佳整数解决方案。

4.结论

研究了两机车间最大完工时间最小化问题的一个新方法。我们考虑单位时间作业，这些作业可以分成批。设置时间被认为是与机器相关的。我们介绍了两种不同情况下的优雅的封闭解。

一个具有挑战性的延伸是设置一个m-Machine Flowshop.．另一个有趣的问题是指2机器jobshop设置。虽然没有发布，但这两个问题都似乎具有类似的性质和结构，并且可能具有批量数及其尺寸的封闭式解决方案。这m机器作业车间案例被认为是强烈的np困难，即使没有设置[12］．因此，未来处理此扩展的研究可能集中于启发式/近似的介绍或开发精确(伪多项式)求解算法。

附录

案子

如前所述，案例分析与本案相似吗同样，我们首先关注的是放松的版本。下界(3．1）对于给定的批次数量K.,仍然成立。与前面的例子一样，达到这个下界的调度在第二台机器上的连续作业之间必须没有空闲时间。的条件仍然有效，从那以后呢这些可以写成基于平等的时间表明确地满足了这些条件，再次领导，连续批次大小之间的恒定差异：．由于所有批次的总大小是N，我们获得以下批量尺寸的以下计划：

请注意，结果计划与所获得的情况相同，以逆转的顺序：最大的批次成为首先，第二至最大的秒，等等。此计划具有与下限相同的Mapespan值（3．1)，因此对于松弛问题和给定K.价值。

maxespan值由

(注意,(a .）与Makespanal值相同（3．3)早些时候获得。)由于函数(a .)是严格凸的，则最优(整数)K.-value是通过一个简单的微分和舍入到最接近的两个整数中的一个得到的(参见3．4） 和 （3．5)．鉴于对轻松问题的最佳解决方案，我们再次考虑整数版本。我们建议先前介绍的舍入程序，即第一个K.-L.分批，剩下的四舍五入L.批次(,)．由于其Mapespan值（由（）以来，整数批量大小的计划是最佳的（由（3．7)与下界(3.6)．我们的最后一个参数指的是整数批的最佳数量。和前面的例子一样，由于完整性和(整数)makespan值由

它被相同的东西最小化了K.值，使松弛版本的目标最小化(a .)．因此，如前所述，最佳批数由(3．4） 和 （3．5)．

我们得出了这种情况下的最优解通过非常相似的（恒定的时间）算法来获得案例的一个非常相似的（恒定的时间）算法．(步骤2略有不同，因为批量大小的序列正在减少。)为了简单起见，我们省略了正式的算法。

例A.1。我们替换S.₁和S.₂在示例3．2：N  =  80,S.₁  =  3,S.₂  =  2. The optimal number of batches (Step1)仍然是6。在步骤2我们获得批量尺寸（对于轻松的问题）：N₁= 15.833,N₂= 14.833,N_3.= 13.833,N_4.  =  12.833,N_5.  =  11.833, andN_6.= 10.833。(注意这个序列与示例中松弛问题得到的序列相反3．2)。最优整数解(步3.)由以下批大小顺序组成:N₁= 16,N₂= 15,N_3.= 14,N_4.= 13，N_5.= 12，N_6.= 10;见图3.．

.发表评论。在设置时间不一定是整数的情况下，找到最佳的批数需要进行搜索。使用的事实是，规模最小的批(现在)必须是非负的，我们得到(在上一种情况下)下面的上界K.：由于搜索仅限于区间[1]内的整数，m]，在这种情况下的总运行时间变为

参考

1. A. Allahverdi, C. T. Ng, T. C. E. Cheng，和M. Y. Kovalyov，“安排时间或成本问题的调查”，欧洲运营研究杂志第187卷，no。3, 985-1032页，2008。视图:出版商的网站|谷歌学者
2. T. C. E. Cheng，B. M.T. Lin和A. Toker，“MapEspan最小化在两台机器流程调度问题中，”海军研究物流(第47卷第40期)2，页128 - 144,2000。视图:出版商的网站|谷歌学者
3. C. A.玻璃，C.N.Potts和V.A.Strusevich，“调度与两台机器流量和开放式商店的顺序工作处理批次，”INFORMS计算杂志，卷。13，不。2，pp。120-137,2001。视图:谷歌学者
4. G. Mosheiov和D. Oron，“关于流店和工作店批量调度的笔记，具有相同的处理时间作业”欧洲运营研究杂志，卷。161，没有。1，pp。285-291,2005。视图:出版商的网站|谷歌学者
5. G. MoSheiov和D. Oron，“与相同的工作开放式批次调度”，欧洲运营研究杂志第187卷，no。3，页1282-1292,2008。视图:出版商的网站|谷歌学者
6. C. T. Ng和M. Y. Kovalyov，“多机流程车间中的批处理和调度”，安排期刊，卷。10，没有。6，PP。353-364,2007。视图:出版商的网站|谷歌学者
7. G. Mosheiov, D. Oron和Y. Ritov，“具有相同处理时间作业的流水车间批量调度”，海军研究物流，卷。51，没有。6，pp。783-799，2004。视图:出版商的网站|谷歌学者
8. 陈建平，“流车间离散批量流的近似方法”，行动研究快报第21卷，没有。139-145, 1997。视图:谷歌学者
9. 陈建平，“双机流程车间的离散批次流”，公司杂志，第37卷，no。2，页160-173,1999。视图:谷歌学者
10. “一种具有可变子块的离散批次流启发式方法”，国际先进制造技术杂志，卷。22，没有。9-10，pp。662-668,2003。视图:出版商的网站|谷歌学者
11. R. G. Vickson，“双机流程车间多产品的最优批量流”，欧洲运营研究杂志(第85卷)3，第556-575页，1995。视图:谷歌学者
12. J. K. Lenstra和A. H.G.G.Rinnooy Kan，“离散优化问题的计算复杂性”离散数学的历史，卷。4，pp。121-140,1979。视图:谷歌学者

版权

版权所有©2009 Lika Ben-Dati等人。这是一篇开放获取的文章创意公共归因许可证，允许在任何媒介上不受限制地使用、分发和复制，只要原稿被适当引用。