《带时间延迟的排序问题综述》由会员分享，可在线阅读，更多相关《带时间延迟的排序问题综述（3页珍藏版）》请在金锄头文库上搜索。
1、带时间延迟的排序问题综述摘 要：近年?恚?排序问题受到多数学者的重视。同时，在理论和实际方面出现很多新模型.关于多工序的工件排序中，通常认为前面的工序完成之后，后面的工序便可开始加工；可是现实并非如此，各工序之间也需要一定的时间延迟。文章介绍了带时间延迟排序问题的研究现状及相关算法。 关键词：排序问题；最优算法；延迟 引言 对于带有时间延迟的排序问题，可分为两类，一类是对工件 Jj的两道工序间至少需要延迟 lj 个单位时间，我们称这类问题为至少时间延迟排序。另一类是前后两道工序间时间延迟刚好为 lj 个单位时间（exact delay） ，我们称这类问题为精确时间延迟排序。目前，关于以上这两类
2、问题的研究，主要集中于单台机和两台机的流水作业问题，并且，多数以极小化最大完工时间为目标（makespan） ，考虑总完工时间的文献很少。 多工序排序问题可以分为无时间延迟（lj=0）流水作业排序问题，带有至少 lj 个单位时间延迟的排序问题，带有精确时间延迟的排序问题。 1 无时间延迟排序问题 对两台机流水作业问题 F2|no-wait|Cmax，Johnson 给出了一个O（n log n）的最优算法。对目标函数是最小化总完工时间问题F2|no-wait|Cj，van Deman 和 Baker 提出一个分支定界算法；Rck证明了这个问题是强 NP-难的。当每个工序的操作时间 Pi，j0，
3、1时，Gonzales 证明 F|no-wait，Pi，j0，1|Cj 是强 NP-完全问题；两台时，Sriskar ajah 和 Ladet 证明 F2|no-wait，Pi，j0，1|Cj 多项式时间可解。Rajendran 和 Chaudhuri 对无时间延迟两台机流水作业排序问题提出一个工件插入启发式算法（insertion heuristic） 。Chen et al. 对无时间延迟两台机流水作业排序问题提出一个遗传算法和一些计算结果。Fink 和 Vo 对无时间延迟 m 台机流水作业排序问题提出一个元启发式算法（metaheuritics） 。 2 至少时间延迟排序问题 以 mak
4、espan 为目标的单台机排序问题，在解不限于排列排序的情况下，Kern 和 Nawijn 证明是 NP-难的，而 Lenstra 证明两台流水作业排序问题 F2|lj|Cmax 是强 NP-难的，DellAmico 给出该问题一个 2-近似多项式时间算法， 并且提出一个禁忌搜索算法。当两道工序加工时间相同时，DellAmico、Vaessens 证明F2|lj，aj=bj|Cmax 是强 NP-难的。Johnson、Mitten 证明了该问题存在最优排列排序（permutation schedule） ；当工件延迟时间相等时， Johnson、Mitten 证明该问题存在一个最优排序是排列排
5、序（permutation schedule） 。当两道工序加工时间相同且时间延迟lj0，l时，Yu 证明 F2|lj0，1，aj=bj|Cmax 是强 NP-难的。进一步，即便两道工序的加工时间均为单位时间，Yu 证明问题F2|ljaj=bj=1|Cmax 仍是强 NP-难的。 3 精确时间延迟排序问题 当第一道工序与第二道工序的加工时间分别等于两个定值时，文献 Farina 和 Neri 对问题 1|exact lj|Cmax 的一种特殊情况提出了一个贪婪算法；Izquierdo-Fuente 和 Casar-Corredera 则对该问题提出了一个神经网络算法。单台机的一些特殊情况，Orman 和Potts 证明是多项式可解的，并且证明即使所有工序加工时间相同，该问题仍然是强 NP-难的。Elshafei et al.基于离散化的时间跨度问题提出一个拉格朗日松弛算法（Lagrange relaxation algorithm） 。Leung 等利用贪婪算法研究延误非增的情形，给出了问题 F2|lj，aj=a，bj=b，a3b|Cj 的最优排序，而对问题F2|lj，aj=a，bj=b，a
