第３０卷 第４期运 筹 与 管 理
Ｖｏｌ．３０，Ｎｏ．４
２０２１年４月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥ
Ａｐｒ．２０２１
收稿日期：２０１９ ０１ １３
基金项目：国家自然科学基金资助项目（１１９０１２５５）；江西省教育厅科技项目（ＧＪＪ１５０４４７）
作者简介：李刚刚（１９８５ ），男，河南省汝州人，讲师，博士学位，组合最优化；鲁习文（１９６２ ），通讯作者，男，教授，博士学位，组合最优化。
李刚刚１， 鲁习文２
（华东理工大学理学院，上海）
摘 要：本文研究了两台机器带柔性维修时间限制的排序问题，其中第一台机器在固定的时间内必须进行维修，而
第二台机器一直可用，目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题，我们给出了一个性能比为的近似算法，并证明了该性能比是紧的。关键词：序；柔性维修；算法；性能比中图分类号：Ｏ２２４ 文章标识码：Ａ 文章编号：１００７ ３２２１（２０２１）０４ ０１２９ ０５ ｄｏｉ：１０．１２００５／ｏｒｍｓ．２０２１．０１５５ ＡｎＡｐｐｒｏｘｉｍａｔｉｏｎＡｌｇｏｒｉｔｈｍｆｏｒＴｗｏ ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍｗｉｔｈ
ＦｌｅｘｉｂｌｅＭａｉｎｔｅｎａｎｃｅｔｏＭｉｎｉｍｉｚｅＭａｋｅｓｐａｎ
ＬＩＧａｎｇ ｇａｎｇ１，ＬＵＸｉ ｗｅｎ
２
（ＥａｓｔＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｃｏｌｌｅｇｅｏｆｓｃｉｅｎｃｅ，Ｓｈａｎｇｈａｉ，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｃｏｎｓｉｄｅｒｓａｔｗｏ ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｆｌｅｘｉｂｌｅｍａｉｎｔｅｎａｎｃｅｗｉｔｈｔｈｅｏｂｊｅｃｔｉｖｅｔｏ
ｍｉｎｉｍｉｚｅｍａｋｅｓｐａｎ．Ｉｎｔｈｅｓｃｈｅｄｕｌｉｎｇｍｏｄｅｌ学习卡
，ｔｈｅｆｉｒｓｔｍａｃｈｉｎｅｎｅｅｄｓｍａｉｎｔｅｎａｎｃｅｄｕｒｉｎｇａｆｉｘｅｄｐｅｒｉｏｄ，ｗｈｉｌｅｔｈｅｏｔｈｅｒｏｎｅｉｓａｖａｉｌａｂｌｅａｌｌｔｈｅｔｉｍｅ．Ｐｒｅｅｍｐｔｉｏｎｉｓｎｏｔａｌｌｏｗｅｄ．Ｗｅｐｒｏｖｉｄｅａｎａｐｐｒｏｘｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍｗｉｔｈｗｏｒｓｔ ｃａｓｅｒａｔｉｏｏｆａｎｄｓｈｏｗｔｈａｔｔｈｅｗｏｒｓｔ ｃａｓｅｒａｔｉｏｉｓｔｉｇｈｔ．Ｋｅｙｗｏｒｄｓ：ｓｃｈｅｄｕｌｉｎｇ；ｆｌｅｘｉｂｌｅｍａｉｎｔｅｎａｎｃｅ；ａｌｇｏｒｉｔｈｍ；ｗｏｒｓｔ ｃａｓｅｒａｔｉｏ
０ 引言
在经典排序模型中，我们一般假设机器是一直可用的。这种假设与实际生产生活不太相符，因为机器在加工工件的过程中可能因为损坏、维修、保养等因素停下来，在这期间机器不能加工任何工件。根据这些实际背景，学者们提出了机器带使用限制
的排序模型。文献Ｓｃｈｍｉｄｔ［１］以及Ｓａｎｌａｖｉｌｌｅ和Ｓｃｈｍｉｄｔ［２］对机器带使用限制的排序问题的一些研究成果做出了综述。Ｌｕｏ和Ｃｈｅｎｇ［３］研究了几个不
同目标下单台机器带可变性不可用时间限制的排序问题，并给出了相应的算法。对于工件带拒绝的排
序问题，Ｌｉ和Ｚｈａｏ［４］
考虑了单台机器带不可用时间
限制的，每个工件都有释放时间，机器在加工过程中
可以拒绝加工某些工件，目标是最小化加工工件中的最大完工时间与所有被拒绝工件的惩罚费用的和，并给出了一个ＦＰＴＡＳ（ＦｕｌｌｙＰｏｌｙｎｏｍｉａｌＴｉｍｅ
ＡｐｐｒｏｘｉｍａｔｉｏｎＳｃｈｅｍｅｓ）。同样，Ｚｈｏｎｇ等［５］
研究了
机器有不可用约束且工件带拒绝的排序问题。
Ｗａｎｇ和Ｌｉｕ［６］研究了单台机器带可变性不可用时
间约束，目标是最小化工件的加权完工时间和的排序问题，其中，机器的不可用时间变化服从Ｗｅｉｂｕｌｌ概率分布的，他们给出了一个分支定界算法来解决
该问题。Ｌｕｏ和Ｊｉ［７］考虑了工件加工时间有线性
恶化率的，目标分别为最小化最大完工时间和最小化完工时间和的机器带使用限制的排序问题，并给
出了相应的算法。Ｘｕ等［８］
研究了目标函数是最小
化工件完工时间和的单台机器带不可用时间限制的排序问题，其中机器不可用时间段的大小是机器负载的函数。Ｄｅｔｔｉ等［９］研究了在一个固定的时间窗内有一个不可用时间段限制的单台机器的排序问题，目标分别是最小化最大完工时间和最小化所有工件的完工时间和，并给出了相应的算法。Ｊｉ等［１０］研究了单台机器带周期性不可用时间限制的排序问题，并给出了相应的近似算法。后来，Ｙｕ等［１１］也研究了该问题，他们比较了ＬＳ（ＬｉｓｔＳｃｈｅｄ ｕｌｉｎｇ）算法，Ｌ
ＰＴ（ＬｏｎｇｅｓｔＰｒｏｃｅｓｓｉｎｇＴｉｍｅＦｉｒｓｔ）算法和ＭＬＰＴ（ＭｏｄｉｆｉｅｄＬｏｎｇｅｓｔＰｒｏｃｅｓｓｉｎｇＴｉｍｅＦｉｒｓｔ）算法在这个问题中的表现性能，并指出这三个算法有相同的性能比。Ｎｅｓｅｌｌｏ等［１２］研究了单台机器带周期性维修时间，工件有安装时间，目标是最小化最大完工时间的排序问题，并给出了相应的解决方案。Ｙｉｎ等［１３］考虑了单台机器带一个维修时间的排序问题，目标是最小化所有延迟工件的个数，他们分别给出了两个拟多项式时间动态规划算法和一个ＦＰＴＡＳ。后来，Ｌｉｕ等［１４］将机器有一个维修时间段的情形扩展到机器有周期性维修时间段的情形，目标函数也是最小化所有延迟工件的个数，他们给出了一个分支定界算法。Ｌｕｏ和Ｌｉｕ［１５］研究了单台机器带不可用约束的排序问题，其中不可用时间段的长度是机器负载的非负递增函数，目标是最小化所有工件的完工时间和，他们给出了一个近似比为的近似算法和一个ＦＰＴＡＳ。Ｃｕｉ和Ｌｕ［１６］考虑了单台机器带柔性不可用时间约束的排序问题，目标是最小化最大完工时间。当工件允许恢复时，他们给出了一个最优多项式时间算法；当工件不可恢复时，他们给出了一个混合整数规划算法和一个启发式算法。
为了满足不同的生产需求，一些研究者将机器带不可用约束的排序问题从单机推广到平行机，并取得了丰富的研究成果。Ｗａｎｇ和Ｃｈｅｎｇ［１７］考虑了两台机器的排序问题，其中一台机器带一个不可用时间段，而另一台机器一直可用，目标是最大化完工工件的个数，他们给出了一个性能比为４／３的近似算法。后来，Ｈａｓｈｅｍｉａｎ等［１８］研究了机器带多个不可用时间段的平行机
排序问题，工件在加工过程中不可中断，目标是最小化最大完工时间，他们给出了一个混合整数规划算法。Ｘｕ等［１９］考虑了两台机器带周期性不可用时间约束的排序问题，其中第一台机器带周期性不可用时间约束，第二台机器一直可用，工件被中断后不允许恢复，目标是最小化最大完工时间，他们证明了ＳＰＴ算法的性能比为３／２。Ｌｉ和Ｌｕ［２０］同样研究了该问题，给出了
一个性能比为４／３的近似算法，并指出该性能比是紧的。Ｌｅｅ和Ｋｉｍ［２１］研究了两台机器带不可用约束的排序问题，目标为最小化所有工件的延迟时间和，并给出了一个分支定界算法。Ｈｕｏ和Ｚｈａｏ［２２］研究了两台机器带不可用约束的单目标和双目标排序问题，每台机器有多个不可用时间段，两台机器的不可用时间段可以同时出现，工件在加工过程中允许恢复，他们给出了相应的算法，并进行了理论分析。Ｋａａｂｉ和Ｈａｒｒａｔｈ［２３］研究了平行机带不可用时间限制的排序问题，每台机器上都有一个不可用时间段，目标是最小化最大完工时间和最小化工件的完工时间和。他们给出了问题的复杂性证明，并对问题的特殊情形给出了最优多项式时间算法。
在流水作业车间里，加工机器可能因为维修、保养等而停止加工工件。对于机器带不可用时间约束，目标为最小化最大完工时间的流水作业排序问题，Ｌｉ等［２４］分别研究了不可用时间段在第一台机器和第二台机器上的两种情形，给出了相应的算法，并证明了算法的性能比都为２。
下面我们描述一下这篇文章中要解决的问题：给定工件集合Ｊ＝｛Ｊ
１
，Ｊ
２
，…，Ｊ
ｎ
｝，工件Ｊ
ｉ
的加工
时间为ｐ
ｉ
，工件在加工过程中不允许中断。将所有工件安排在两台加工机器上加工，其中第一台机器在Δ时间
内必须有一次维修，即两次维修时刻之间的间隔不能大于Δ，每次维修时间长为Ｔ，而第二台机器一直可用，目标是最小化最大完工时间。我们将在第二部分给出算法，分析最优解和算法得到的解之间的关系，给出性能比分析；文章第三部分将给出总结与展望。
１ 算法设计与分析
算法Ｈ：将所有工件按照ＬＰＴ规则尽可能早地安排在机器Ｍ１和Ｍ２上加工。
令π表示由算法Ｈ生成的时间表。令
π（Ｍ１）＝Ｂ
１
（π），Ｔ，Ｂ
２
（π），Ｔ，…，Ｔ，Ｂ
ｊ
（π），Ｔ，…，
Ｂ
ｒ
（π），其中Ｂ
ｊ
（π）和ｒ分别表示在时间表π中，机器Ｍ１上第ｊ个可用时间段中加工工件的集合和占用可用时间段的总数目。记π 为一个最优时
间表。同样，可以令π （Ｍ１）＝Ｂ
１
（π ），Ｔ，Ｂ
２
（π ），
Ｔ，…，Ｔ，Ｂ
ｊ
（π ），Ｔ，…，Ｂ
ｈ
（π ），其中Ｂ
ｊ
p2p网络电视录像专家（π ）和ｈ表示在时间表π 中，机器Ｍ１上第ｊ个可用时间段中工件的集合和占用可用时间段的总数目。下面我们举一个实例来简单介绍一下算法Ｈ：
０
３
１运 筹 与 管 理 ２０２１年第３０卷
假设总共有７个工件，其中ｐ１＝４，ｐ２＝３，ｐ３＝２０，ｐ４＝４，ｐ５＝３，ｐ６＝３，ｐ７＝３，Δ＝６。机器的维修时间长为Ｔ＝４。按照算法Ｈ的规则，由于ｐ３＞Δ，Ｊ３只能安排在Ｍ２上加工；ｐ１＜Δ，Ｊ１可以被安排在Ｍ１加工；由于ｐ１＋ｐ４＞Δ，Ｊ４只能被安排在一个维修之后加工；同理，ｐ４＋ｐ５＞Δ，Ｊ５只能被安排在一个维修之后加工；由于ｐ５＋ｐ６＝Δ，Ｊ５和ｊ６将被安排在Ｍ１上同一个可用区间内一起加工；Ｊ２和Ｊ７将被安排在Ｍ２上一起加工，从而它们可以尽可能早地完工。计算可得ｃｍａｘ（
π）＝２６，ｃｍａｘ
（π ）＝２４。引理１
∑水下呼吸器
Ｊｉ∈Ｂｊ
玻璃钢套管（π）ｐｉ＞
Δ
２
，ｊ＝１，２，…，ｒ－１。证明 不妨设Ｊｓ为Ｂｊ中最后加工的工件。根据算法的规则可知，ｐｓ＋１ ｐｓ。若∑
Ｊｉ∈Ｂｊ
（π）ｐｉ
Δ２
，则ｐｓ＋１ ｐｓ
Δ
２。由此可得，∑Ｊｉ∈Ｂｊ
（π）ｐｉ＋ｐｓ＋１ Δ。可推出Ｊｓ＋１∈Ｂｊ（π）。这与Ｊｓ是Ｂｊ中最后加工的工件矛盾。因此，∑Ｊｉ∈Ｂｊ
（π）ｐｉ Δ２。现在我们先考虑一个特殊的问题，记为问题Ｉ：将工件Ｊ１，Ｊ２，…，Ｊｋ（ｐｊ Δ，１ ｊ ｋ）安排在机器Ｍ１上加工，目标是最小化工件的最大完工时间。记σ为问题Ｉ中在工件
不允许中断的前提下由ＬＰＴ规则生成的时间表，ＬＢ（Ｉ）为问题Ｉ中允许工件中断时得到的最优值。不妨记时间表σ＝（Ｂ１，Ｔ，Ｂ２，Ｔ，…，Ｔ，Ｂｓ），其中Ｔ和ｓ分别为机器维修时间段的长度和工件占用可用区间的个数。我们可以得到以下引理：
引理２ Ｃｍａｘ
（σ） ２ＬＢ（Ｉ）。证明 对于问题Ｉ，时间表σ＝（Ｂ１，Ｔ，Ｂ２
，Ｔ，…，Ｔ，Ｂｓ），由引理１可知，∑Ｊｉ∈Ｂｊ
ｐ
ｉ Δ／２，ｊ＝１，２，…，ｓ－１。
若ｓ＝２ｍ，可知 ＬＢ（Ｉ）
（ｓ－２）
２（Δ＋Ｔ）＋（Δ＋Ｔ）＝（ｍ－１）（Δ＋Ｔ）＋（Δ＋Ｔ）
１
２Ｃｍａ
ｘ（σ）若ｓ＝２ｍ＋１，可知 ＬＢ（Ｉ）
（ｓ－１）
２（Δ＋Ｔ）＋∑Ｊｉ∈Ｂｓ
ｐｉ
＝ｍ（Δ＋Ｔ）＋∑Ｊｉ∈Ｂｓ
ｐｉ １
２Ｃｍａ
ｘ
（σ）因此，Ｃｍａｘ
（σ） ２ＬＢ（Ｉ）。引理３ 当ｒ＞２时，若π不是最优时间表，可
得｜Ｃ２ｍａｘ（π）－Ｃ１
ｍａｘ
（π）｜ １２
Ｃｍａｘ（π
）。证明 不妨设时间表π中最后完工的工件为Ｊｌ。若ｐｌ＞Δ，由算法Ｈ可知安排在机器Ｍ２上加工的每个工件的加工时间都大于Δ，可知最优时间表的表长不小于工件Ｊｌ的完工时间，这可推出π是一个最优时间表。因为π不是最优时间表，所以ｐｌ
Δ。（１）若Ｃ２ｍａｘ（π） Ｃ１
ｍａｘ（
π），由算法Ｈ可得Ｃ１ｍａｘ（π）－Ｃ２ｍａｘ
（π） ｐｌ，又由ｐｌ １２
Ｃｍａｘ（π
），可得Ｃ１ｍａｘ（π）－Ｃ２
ｍａｘ（
π） １２Ｃｍａｘ（π
）。若ｐｌ＞１２
Ｃｍａｘ
（π
），则工件集中至多有两个工件的加工时间大于等于ｐｌ。由此可得，π是一个最优时间表。因此，ｐｌ
１２
Ｃｍａｘ（π
）。（２）若Ｃ２ｍａｘ（π）＞Ｃ１ｍａｘ（π），则Ｃ２ｍａｘ（π）－Ｃ１
ｍａｘ
（π） Ｔ＋Δ。由ｒ＞２和Ｃ２ｍａｘ（π）＞Ｃ１
ｍａｘ（π），可推出Ｃｍａｘ（π
） ２（Ｔ＋Δ），所以，Ｃ２ｍａｘ（π）－Ｃ１ｍａｘ
（π） Ｔ＋Δ
１２
Ｃｍａｘ（π
）。定理１ Ｃｍａｘ
（π） ３２
Ｃｍａｘ（π
）。证明 不妨设在时间表π中最后完工的工件为Ｊｌ。若ｐｌ＞Δ，由算法可知安排在机器Ｍ２上加工的每个工件的加工时间都大于Δ，可知最优时间表的表长不小于工件Ｊｌ的完工时间，这可推出π是一个最优时间表。否则，我们用反证法证明该定理。假设Ｃｍａｘ（π）＞３２
Ｃｍａｘ（π
），可知π不是最优时间表，因此ｐｌ
１２
Ｃｍａｘ（π ）。令π（Ｍ１）＝（Ｂ１，Ｔ，Ｂ２，Ｔ，…，Ｔ，Ｂｒ），其中Ｔ和ｒ分别为机器Ｍ１的维修时间长度和时间表π中机器Ｍ１上工件占用的可用区间段的个数。我们将从以下两个方面证明该定理：
情形１ Ｃｍａｘ（π）＝Ｃ２ｍａｘ（π）＞３２Ｃｍａｘ
（π
）。若ｒ＝１，则∑Ｊｉ∈Ｂ１ｐｉ＋１２Ｃｍａｘ（π
） ∑Ｊｉ∈Ｂ１
ｐｉ＋ｐｌ＞Δ。由此可推出Ｃｍａｘ（π ）＞Ｃｍａｘ（
π ），这与π
是最优时间表矛盾，所以结论成立。
若ｒ＝２，则
（ａ）当Ｃ２ｍａｘ（π）－Ｃ１
ｍａｘ（π） ２ｐｌ时，
可知１
３１第４期 李刚刚，等：目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法
Ｃｍａｘ（π ） Ｃ２ｍａｘ
（π）－ｐｌ。结合Ｃｍａｘ（π
）＞Δ＋ｐｌ ２ｐｌ
，可得Ｃ２
ｍａｘ
（π）Ｃｍａｘ（π ） １＋ｐｌ
Ｃｍａｘ
（π
） ３２（ｂ）当２ｐｌ＜Ｃ２
ｍａｘ
（π）－Ｃ１
ｍａｘ
（π） ３ｐｌ时，若ｐｌ
＞Δ／２，可推出Ｃ２ｍａｘ
（π）－Ｃｍａｘ（π
） Δ－ｐｌ ｐｌ。再结合Ｃ２
ｍａｘ
（π） ４ｐｌ
，可推出Ｃ２
ｍａｘ
（π
）Ｃｍａｘ（π
） １＋ｐｌ
Ｃ２ｍａｘ（π）－ｐｌ
３２若ｐｌ Δ／２，可推出Ｃ２
ｍａｘ
（π） ５ｐｌ和Ｃ
２
ｍａｘ
（π）－Ｃｍａｘ（π
） ｐｌ＋δ，其中０ δ ｐｌ
／２。因此，Ｃ２
ｍａｘ
（π）Ｃｍａｘ（π ） １＋ｐｌ＋
δＣ２ｍａｘ
（π）－ｐｌ－δ ３
２（ｃ）当Ｃ２ｍａｘ（π）－Ｃ１
ｍａｘ（π）＞３ｐｌ时，可知Ｃｍａｘ（π ） ４ｐｌ和Ｃ２ｍａｘ（π）－Ｃｍａｘ（π
）
２ｐｌ
。所以，
Ｃ２
ｍａｘ
（π）Ｃｍａｘ（π ） １＋ｐｌ
Ｃｍａｘ
（π
） ３
２若ｒ＞２，由引理３可知
Ｃ２ｍａｘ
（π）－Ｃ１
ｍａｘ
（π） １２
Ｃｍａｘ
（π ）再由假设Ｃ２ｍａｘ
（π）＞３２
Ｃｍａｘ（π
），可推出Ｃ１ｍａｘ
（π）＞Ｃｍａｘ
（π
）。再结合引理２，可知Ｃｍａｘ（π ）＞Ｃｍａｘ（π
）。这就推出了矛盾，所以Ｃ２假山的堆叠
ｍａｘ
（π） ３２
Ｃｍａｘ（π
）。情形２ Ｃｍａｘ（π）＝Ｃ１ｍａｘ（π）＞３２
Ｃｍａｘ
（π
）。由算法Ｈ可知，Ｃ１ｍａｘ（π）－Ｃ２
ｍａｘ
（π） ｐｌ。由此可推出Ｃ２ｍａｘ（π） Ｃ１ｍａｘ（π）－ｐｌ＞３２Ｃｍａｘ（π
）－ｐｌ
由ｐｌ
１２Ｃｍａｘ（π
），可知Ｃ１ｍａｘ（π）－ｐｌ＞３２
Ｃｍａｘ（π
）－ｐｌ
３２Ｃｍａｘ（π ）－１２
Ｃｍａｘ（π
）＝Ｃｍａｘ（π ）。结合引理２，可知Ｃｍａｘ（π ）＞Ｃｍａｘ
（π ）。这与π
是最优时间表矛盾，因此结论成立。定理２ 算法Ｈ的性能比是紧的。
证明 工件集中总共有四个工件Ｊ１，Ｊ２，Ｊ３
，Ｊ４，ｐ１＝ｐ２＝
Δ２＋ε，ｐ３＝ｐ４＝Δ２
，Ｔ＝４Δ。其中ε是一个足够小的正数。由算法Ｈ可得Ｃｍａｘ
（π）＝３
２
Δ＋ε，而最优值Ｃｍａｘ
（π
）＝Δ＋２ε。因此，Ｃｍａｘ
（π）Ｃｍａｘ
（π
）＝３
２Δ＋
εΔ＋２ε→３２（ε→０）２ 总结与展望：
本文研究了两台机器带柔性使用限制的排序问题，其中第一台机器在Δ时间内必须有一次维修，即两次维修时刻之间的间隔不能大于Δ，每次维修时间长为Ｔ，而第二台机器一直可用，工件在加工过程中不允许中断，目标是最小化最大完工时间。该模型比较符合实际生产背景，对该模型的研究可以为现实生产生活提供一定的理论指导作用。对于该问题，我们基于经典ＬＰＴ算法的思想，结合该问题最优解的一些性质，给出了一个性能比为的近似算法，并证明了该算法的性能比是紧的。在下一步的研究工作中，我们将考虑其它目标函数，例如Ｌｍａｘ和ΣＣｊ。这种模型的不足之处是每个维修时间长度都是固定的，而在现实生产中，机器的维修时间可能并不是恒定的，大部分情况下，机器的维修时间长度与机器的负载有关系。一般来讲，随着机器负载的增加，机器越容易出现故障，并且维修时间可能会越长。因此，在今后的研究工作中，我们将考虑机器的维修时间长度是机器负载的某个函数的排序模型，以及带运输的加工机器有柔性使用限制的供应链排序问题，我们将为这些问题设计算法并分析算法的性能，期望能够得到比较好的结果。参考文献：
［１］ＳｃｈｍｉｄｔＧ．Ｓｃｈｅｄｕｌｉｎｇｗｉｔｈｌｉｍｉｔｅｄｍａｃｈｉｎｅａｖａｉｌａｂｉｌｉｔｙ
［Ｊ］．ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，２００
０，１２１：１ １５．［２］ＳａｎｌａｖｉｌｌｅＥ，ＳｃｈｍｉｄｔＧ．Ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｗｉｔｈａｖａｉｌ
ａｂｉｌｉｔｙｃｏｎｓｔｒａｉｎｔｓ
［Ｊ］．ＡｃｔａＩｎｆｏｒｍａｔｉｃａ，１９９８，３５：７９５ ８１１．［３］ＬｕｏＷＣ，ＣｈｅｎｇＴＣＥ，ＪｉＭ．Ｓｉｎｇｌｅ ｍａｃｈｉｎｅｓｃｈｅｄｕ
ｌｉｎｇｗｉｔｈａｖａｒｉａｂｌｅｍａｉｎｔｅｎａｎｃｅａｃｔｉｖｉｔｙ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆ＩｎｄｕｓｔｒｉａｌＥｎｇｉｎｅｅｒｉｎｇ，２０１５，７９：１６８ １７４．［４］ＬｉＷＸ，ＺｈａｏＣＬ．Ｄｅｔｅｒｉｏｒａｔｉｎｇｊｏｂｓｓｃｈｅｄｕｌｉｎｇｏｎａ
ｓｉｎｇｌｅｍａｃｈｉｎｅｗｉｔｈｒｅｌｅａｓｅｄａｔｅｓ，ｒｅｊｅｃｔｉｏｎａｎｄａｆｉｘｅｄｎｏｎ ａｖａｉｌａｂｉｌｉｔｙｉｎｔｅｒｖａｌ［Ｊ］．ＪｏｕｒｎａｌｏｆＡｐｐｌｉｅｄＭａｔｈｅ
ｍａｔｉｃｓａｎｄＣｏｍｐｕｔｉｎｇ
，２０１５，４８：５８５ ６０５．［５］ＺｈｏｎｇＸＬ，ＯｕＪＷ，ＷａｎｇＧＱ．Ｏｒｄｅｒ
ａｃｃｅｐｔａｎｃｅａｎｄ
ｓｃｈｅｄｕｌｉｎｇｗｉｔｈｍａｃｈｉｎｅａｖａｉｌａｂｉｌｉｔｙｃｏｎｓｔｒａｉｎｔｓ［Ｊ］．ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ，２０１４，２３２：４３５ ４４１．［６］ＷａｎｇＳＪ，ＬｉｕＭ．Ａｂｒａｎｃｈａｎｄｂｏｕｎｄａｌｇｏｒｉｔｈｍｆｏｒ
ｓｉｎｇｌｅ ｍａｃｈｉｎｅｐｒｏｄｕｃｔｉｏｎｓｃｈｅｄｕｌｉｎｇｉｎｔｅｇｒａｔｅｄｗｉｔｈｐｒｅ ｖｅｎｔｉｖｅｍａｉｎｔｅｎａｎｃｅｐｌａｎｎｉｎｇ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌ
２
３１运 筹 与 管 理 ２０２１年第３０卷
ｏｆＰｒｏｄｕｃｔｉｏｎＲｅｓｅａｒｃｈ，２０１３，５１：８４７ ８６８．
［７］ＬｕｏＷＣ，ＪｉＭ．Ｓｃｈｅｄｕｌｉｎｇａｖａｒｉａｂｌｅｍａｉｎｔｅｎａｎｃｅａｎｄｌｉｎｅａｒｄｅｔｅｒｉｏｒａｔｉｎｇｊｏｂｓｏｎａｓｉｎｇｌｅｍａｃｈｉｎｅ［Ｊ］．Ｉｎｆｏｒ ｍａｔｉｏｎＰｒｏｃｅｓｓｉｎｇＬｅｔｔｅｒｓ，２０１５，１１５：３３
３９．
［８］ＸｕＤＨ，ＷａｎＬ，ＬｉｕＡＨ，ＹａｎｇＤＬ．Ｓｉｎｇｌｅｍａｃｈｉｎｅｔｏｔａｌｃｏｍｐｌｅｔｉｏｎｔｉｍｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｗｏｒｋｌｏａｄ ｄｅｐｅｎｄｅｎｔｍａｉｎｔｅｎａｎｃｅｄｕｒａｔｉｏｎ［Ｊ］．Ｏｍｅｇａ，２０１５，５２：１０１ １０６．
［９］ＤｅｔｔｉＰ，ＮｉｃｏｓｉａＧ，ＰａｃｉｆｉｃｉＡ，ＬａｒａｄｅＧＺＭ．Ｒｏｂｕｓｔｓｉｎｇｌｅｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｗｉｔｈａｆｌｅｘｉｂｌｅｍａｉｎｔｅｎａｎｃｅａｃｔｉｖｉｔｙ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２０１９，１０７：１９ ３１．
［１０］ＪｉＭ，ＨｅＹ，ＣｈｅｎｇＴＣＥ．Ｓｉｎｇｌｅ ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｗｉｔｈｐｅｒｉｏｄｉｃｍａｉｎｔｅｎａｎｃｅｔｏｍｉｎｉｍｉｚｅｍａｋｅｓｐａｎ［Ｊ］．
Ｃｏｍｐｕｔｅｒｓ＆ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２００７，３４：１７６４ １７７０．［１１］ＹｕＸＹ，ＺｈａｎｇＹＬ，ＳｔｅｉｎｅｒＧ．Ｓｉｎｇｌｅ ｍａｃｈｉｎｅｓｃｈｅｄ ｕｌｉｎｇｗｉｔｈｐｅｒｉｏｄｉｃｍａｉｎｔｅｎａｎｃｅｔｏｍｉｎｉｍｉｚｅｍａｋｅ
ｓｐａｎ
ｒｅｖｉｓｉｔｅｄ［Ｊ］．ＪｏｕｒｎａｌｏｆＳｃｈｅｄｕｌｉｎｇ，２０１４，１７：
２６３ ２７０．
［１２］ＮｅｓｅｌｌｏＶ，ＳｕｂｒａｍａｎｉａｎＡ，ＢａｔｔａｒｒａＭ，ＬａｐｏｒｔｅＧ．Ｅｘａｃｔｓｏｌｕｔｉｏｎｏｆｔｈｅｓｉｎｇｌｅ ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ
ｗｉｔｈｐｅｒｉｏｄｉｃｍａｉｎｔｅｎａｎｃｅｓａｎｄｓｅｑｕｅｎｃｅ ｄｅｐｅｎｄｅｎｔ
ｓｅｔｕｐｔｉｍｅｓ［Ｊ］．ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌ
Ｒｅｓｅａｒｃｈ，２０１８，２６６：４９８ ５０７．
［１３］ＹｉｎＹＱ，ＸｕＪＹ，ＣｈｅｎｇＴＣＥ，ＷｕＣＣ，ＷａｎｇＤＪ．Ａｐｐｒｏｘｉｍａｔｉｏｎｓｃｈｅｍｅｓｆｏｒｓｉｎｇｌｅ ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇ
ｗｉｔｈａｆｉｘｅｄｍａｉｎｔｅｎａｎｃｅａｃｔｉｖｉｔｙｔｏｍｉｎｉｍｉｚｅｔｈｅｔｏｔａｌ
ａｍｏｕｎｔｏｆｌａｔｅｗｏｒｋ［Ｊ］．ＮａｖａｌＲｅｓｅａｒｃｈＬｏｇｉｓｔｉｃｓ，
２０１６，６３：１７２ １８３．
［１４］ＬｉｕＭ，ＷａｎｇＳＪ，ＣｈｕＣＢ，ＣｈｕＦ．Ａｎｉｍｐｒｏｖｅｄｅｘａｃｔａｌｇｏｒｉｔｈｍｆｏｒｓｉｎｇｌｅ ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｔｏｍｉｎｉｍｉｚｅｔｈｅ
ｎｕｍｂｅｒｏｆｔａｒｄｙｊｏｂｓｗｉｔｈｐｅｒｉｏｄｉｃｍａｉｎｔｅｎａｎｃｅ［Ｊ］．
ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＰｒｏｄｕｃｔｉｏｎＲｅｓｅａｒｃｈ，２０１６，５４：
３５９１ ３６０２．
［１５］ＬｕｏＷＣ，ＬｉｕＦ．Ｏｎｓｉｎｇｌｅ ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｗｉｔｈｗｏｒｋｌｏａｄ ｄｅｐｅｎｄｅｎｔｍａｉｎｔｅｎａｎｃｅｄｕｒａｔｉｏｎ［Ｊ］．Ｏｍｅｇａ，
２０１７，６８：１１９ １２２．［１６］ＣｕｉＷＷ，ＬｕＺＱ．Ｍｉｎｉｍｉｚｉｎｇｔｈｅｍ
ａｋｅｓｐａｎｏｎａｓｉｎｇｌｅｍａｃｈｉｎｅｗｉｔｈｆｌｅｘｉｂｌｅｍａｉｎｔｅｎａｎｃｅｓａｎｄｊｏｂｓ’
ｒｅｌｅａｓｅｄａｔｅｓ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，
电蒸汽发生器蒸箱２０１７，８０：１１ ２２．
［１７］ＷａｎｇＸＬ，ＣｈｅｎｇＴＣＥ．Ａｈｅｕｒｉｓｔｉｃｆｏｒｓｃｈｅｄｕｌｉｎｇｊｏｂｓｏｎｔｗｏｉｄｅｎｔｉｃａｌｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｗｉｔｈａｍａｃｈｉｎｅ
ａｖａｉｌａｂｉｌｉｔｙｃｏｎｓｔｒａｉｎｔ［Ｊ］．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆ
ＰｒｏｄｕｃｔｉｏｎＥｃｏｎｏｍｉｃｓ，２０１５，１６１：７４ ８２．
［１８］ＨａｓｈｅｍｉａｎＮ，ＤｉａｌｌｏＣ，ＶｉｚｖáｒｉＢ．Ｍａｋｅｓｐａｎｍｉｎｉｍｉ ｚａｔｉｏｎｆｏｒｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｓｃｈｅｄｕｌｉｎｇｗｉｔｈｍｕｌｔｉｐｌｅ
ａｖａｉｌａｂｉｌｉｔｙｃｏｎｓｔｒａｉｎｔｓ［Ｊ］．ＡｎｎａｌｓｏｆＯｐｅｒａｔｉｏｎｓ
Ｒｅｓｅａｒｃｈ，２０１４，２１３：１７３ １８６．
［１９］ＸｕＤＨ，ＣｈｅｎｇＺＭ，ＹｉｎＹＱ，ＬｉＨＸ．Ｍａｋｅｓｐａｎｍｉｎｉｍｉｚａｔｉｏｎｆｏｒｔｗｏｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｓｃｈｅｄｕｌｉｎｇｗｉｔｈａ
ｐｅｒｉｏｄｉｃａｖａｉｌａｂｉｌｉｔｙｃｏｎｓｔｒａｉｎｔ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａ
ｔｉｏｎｓＲｅｓｅａｒｃｈ，２００９，３６：１８０９ １８１２．
［２０］ＬｉＧＧ，ＬｕＸＷ．Ｔｗｏ ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｗｉｔｈｐｅｒｉｏｄ ｉｃａｖａｉｌａｂｉｌｉｔｙｃｏｎｓｔｒａｉｎｔｓｔｏｍｉｎｉｍｉｚｅｍａｋｅｓｐａｎ［Ｊ］．
ＪｏｕｒｎａｌｏｆＩｎｄｕｓｔｒｉａｌａｎｄＭａｎａｇｅｍｅｎｔＯｐｔｉｍｉｚａｔｉｏｎ，
２０１５，１１：６８５ ７００．
［２１］ＬｅｅＪＹ，ＫｉｍＹＤ．Ａｂｒａｎｃｈａｎｄｂｏｕｎｄａｌｇｏｒｉｔｈｍｔｏｍｉｎｉｍｉｚｅｔｏｔａｌｔａｒｄｉｎｅｓｓｏｆｊｏｂｓｉｎａｔｗｏｉｄｅｎｔｉｃａｌ ｐａｒａｌ
ｌｅｌ ａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈａｍａｃｈｉｎｅａｖａｉｌａｂｉｌｉ
ｔｙｃｏｎｓｔｒａｉｎｔ［Ｊ］．ＪｏｕｒｎａｌｏｆｔｈｅＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ
Ｓｏｃｉｅｔｙ，２０１５，６６：１５４２ １５５４．
［２２］ＨｕｏＹＭ，ＺｈａｏＨＲ．Ｔｗｏｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｓｕｂｊｅｃｔｔｏａｒｂｉｔｒａｒｙｍａｃｈｉｎｅａｖａｉｌａｂｉｌｉｔｙｃｏｎｓｔｒａｉｎｔ［Ｊ］．Ｏｍｅｇａ，
２０１８，７６：１２８ １３６．
［２３］ＫａａｂｉＪ，ＨａｒｒａｔｈＹ．Ｓｃｈｅｄｕｌｉｎｇｏｎｕｎｉｆｏｒｍｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｗｉｔｈｐｅｒｉｏｄｉｃｕｎａｖａｉｌａｂｉｌｉｔｙｃｏｎｓｔｒａ
ｉｎｔｓ［Ｊ］．
ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＰｒｏｄｕｃｔｉｏｎＲｅｓｅａｒｃｈ，２０１９，５７：
２１６ ２２７．
［２４］ＬｉＤＢ，ＣｈｅｎＫＪ，ＷａｎｇＸ．Ｐｒｏｐｅｒｔｉｅｓｏｆｔｗｏ ｍａｃｈｉｎｅｎｏ ｗａｉｔｆｌｏｗ ｓｈｏｐｓｃｈｅｄｕｌｉｎｇｗｉｔｈａｎｏｎ ｒｅｓｕｍａｂｌｅ
ｕｎａｖａｉｌａｂｌｅｉｎｔｅｒｖａｌ［Ｊ］．ＪｏｕｒｎａｌｏｆＩｎｄｕｓｔｒｉａｌａｎｄ
ＰｒｏｄｕｃｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，２０１７，３４：２３２ ２３８．
３
３
１
第４期 李刚刚，等：目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法
