指派问题是一个比较经典的最优化问题，一直以来都吸引着很多人对其进行研究。本论文考虑max-min型限制性指派问题，简称为max-minCAP。该问题是这样描述的：有n项工作U=｛u1,u2，…，un｝，以及m台机器V=｛u1,u2，…，um｝，对于每项工作ui，都有一个集合N（ui）={vj∈V｜ui能在机器vj上完成｝，N（ui）（）V。每项工作ui对于任何一台能完成它的机器有一个相同的花费费用t（ui）以及一个相同的效益p（ui），要求一项工作只能分配给一台机器做，被安排完成的所有工作的总花费不超过T，目标是寻找一个最优工作分配方案，使得机器上产生的最少效益值达到最大。　　 本论文证明了max-minCAP强NP-难的，之后对于它的两个特殊情况进行了研究：（1）I-Pmax-minCAP，即是当max-minCAP中对任意ui都有p（ui）=1时的特殊情况，本文给出了一个时间复杂度为O（log2｜U｜·（｜E｜+｜U｜+｜V｜）·｜U｜）的算法；（2）I-Tmax-minCAP，即是当max-minCAP中对任意ui有t（ui）=1时的特殊情况，本文给出它的一个时间复杂度为O（｜u｜·max{｜E｜，｜U｜+｜V｜｝）的启发式算法。最后，对于max-minCAP中没有总花费限制并且对任意ui都有p（ui）=1的情况I-Pmax-minAP，本文给出了一个证明，证明Harvey等人提出的均衡指派问题[1]的最优解也是I-Pmax-minAP的一个最优解。