The simple and multiple job assignment problems

摘要

This paper addresses two real-life assignment problems. In both cases, the number of employees to whom tasks should be assigned is significantly greater than the number of tasks. In the simple job assignment problem, at most one task (job) should be assigned to each employee; this constraint is relaxed in the multiple job assignment problem. In both cases, the goal is to minimize the time the last task is completed: these problems are known as Bottleneck Assignment Problems (BAPs for short).