N×2N瓶颈指派问题及其阀门(threshold)算法

N×2N Bottleneck Assignment Problems with the Threshold Algorithm

讨论把2N项任务(或工件)指派(安排)给N个人(或机器)的问题.已知人i处理(或加工)任务j的时间花费是cij,i=1,2,…,N,j=1,2,…,2N,要求每人恰承担2项任务,每项任务恰由1个人承担.怎样分派任务,使完成任务最慢的人所花的时间最少.

Consider a set of 2N jobs and a group of N persons （or machines） with processing time （or cost） cij if person i is assigned job j. Each person is required to be assigned exactly 2 jobs and each job is assigned to exactly one person. The objective function is the largest total processing time of any person. The problem is to assign the 2N jobs to N persons in such a way that the objective value is minimized.