Abstract: The classical assignment problem studies the binary matchings between the resources and tasks. As a generalization, the 3-dimensional assignment problem studies the triple matchings between the resources, tasks, and services. The former is well solved by efficient algorithms, while the latter is a well-known NP-hard problem. This paper discusses a two-stage assignment problem between these two levels, which is a special 3-dimensional assignment problem that can be decomposed into two-stage decision. Several polynomial-time algorithms are presented.

Key words: combinatorial optimization, assignment problem, two-stage assignment problem, special 3-dimensional matching

摘要： 经典的指派问题是研究资源与任务的二元匹配。作为推广,三维指派问题是研究资源、任务与作业的三元匹配。前者已有成熟的有效算法,后者是著名的NP困难问题。本文讨论介于二者之间的一类二阶段指派问题,即可分解为二阶段决策的特殊三维匹配问题,给出多项式时间算法。

关键词: 组合最优化, 指派问题, 二阶段指派问题, 特殊三维匹配