高级检索

    刘朝晖. 关于工件组的两机自由作业时间表问题[J]. 华东理工大学学报(自然科学版), 2000, (6): 665-669.
    引用本文: 刘朝晖. 关于工件组的两机自由作业时间表问题[J]. 华东理工大学学报(自然科学版), 2000, (6): 665-669.
    Scheduling Groups of Jobs in Two-machine Open Shop[J]. Journal of East China University of Science and Technology, 2000, (6): 665-669.
    Citation: Scheduling Groups of Jobs in Two-machine Open Shop[J]. Journal of East China University of Science and Technology, 2000, (6): 665-669.

    关于工件组的两机自由作业时间表问题

    Scheduling Groups of Jobs in Two-machine Open Shop

    • 摘要: 讨论关于工件组的两机自由作业时间表的加工全长问题,无论是对于成组加工情形还是分组情形,该问题都可以被证明是NP困难的。对于成组加工情形,设计了一个性能比为5/4的近拟算法,该算法生成的时间表作为分组情形的解,性能比仍能保持为5/4。此外,还讨论了如何最优地求解只有一个工件组的情形。

       

      Abstract: This paper is concerned with the makespan problem of scheduling groups of jobs in two machine open shop. The problem is known as NP hard no matter whether group sub lotting is admissible or not. We obtain an approximation algorithm which generates a GT schedule (in which no group is split) with the worst case performance ratio 5/4, even when the GT schedule is used as a solution to the group sub lotting case. Besides, we give a polynomial algorithm to solve the one group case to optimality.

       

    /

    返回文章
    返回