最小化完工时间和为第一目标的多目标不相容分批排序

Multi-Criteria Batch Scheduling with Incompatible Job Families and the Total Completion Time as the Primary Criterion

研究以工件总完工时间为第1目标的多目标不相容分批排序问题,对于加权总完工时间和最大延误为第2目标的排序问题给出了多项式时间的算法。对于误工工件个数和工件总延误为第2目标的排序问题的不同情况进行了讨论,给出了多项式时间算法或证明了其复杂性。

The bicriterion scheduling with incompatible job families and the total completion time as the primary criterion is discussed.Polynomial time algorithms are developed for the problems with the total weighted completion time and the maximum tardiness as the secondary criterion.For the different cases of the problems with the number of tardy jobs and the total tardiness as the secondary criterion,polynomial time algorithms or complexity proofs are presented,respectively.