Applications of Combinatorial Optimization, 2nd Edition

Chapter 11

Multicriteria Task Allocation to Heterogenous Processors with Capacity and Mutual Exclusion Constraints

The problem considered is a generalization of the classical assignment problem so as to take into account mutual exclusion constraints that restrict the possibilities of allocating tasks to processors because of incompatible groups of tasks. These groups are defined relative to each processor, each processor only being able to process at most one task from the group considered. Each processor can usually process a certain number of tasks for a zero cost, with the possibility of its capacity being increased at the price of marginal non-decreasing costs. Each task must be assigned to one and only one processor with certain “preferences”. These are formalized by dissatisfaction indices. The quality of an allocation is evaluated with the help of three criteria: g₁ – the maximum dissatisfaction of the tasks; g₂ – the total dissatisfaction of the tasks; g₃ – the total cost of processing the tasks using the processors. When no feasible allocation exists, the tasks and processors that make up the “blocking configuration” are identified and all unblocking actions are revealed. Several results with regard to blocking configurations and unblocking actions are given. An interactive procedure for exploring non-dominated solutions is described and illustrated through two examples solved using a specially designed program.

11.1. Introduction and formulation of the problem

We consider: ...