Abstract: All jobs must be grouped into some stages and carried out successively, but jobs at the same stage can be commenced simultaneously. In this case, this paper researches how to allocate all jobs to the existing persons so as to minimize the completion time subject to the minimum makespan. A monotone decreasing iterative algorithm, which can obtain the precise optimal solution and has good computational efficiency, is proposed by introducing cubic detection matrix.

Key words: assignment problem, bi-objective, cubic detection matrix, iterative algorithm, precise optimal solution

摘要： 针对所有工作必须分阶段依次完成，但同一个阶段的工作可以同时进行的情况下，如何分配现有人员来承担这些工作，才能使得完成所有工作的工期最短，并在此前提下使花费的总用时最少的分配问题，通过引入立方检测矩阵，给出了一种单调下降的迭代算法。该算法不但能获取精确最优解，而且有很好的计算效率。

关键词: 分配问题, 双层目标, 立方检测矩阵, 迭代算法, 精确最优解