Multi-criteria assignment problem with incompatibility and capacity constraints |
| |
Authors: | Bernard Roy Roman Słowiński |
| |
Institution: | (1) LAMSADE, University of Paris Dauphine, 75775 Paris, France;(2) Institute of Computing Science, Poznań University of Technology, 60-965 Poznań, Poland;(3) Institute for Systems Research, Polish Academy of Sciences, 01-447 Warsaw, Poland |
| |
Abstract: | The considered assignment problem generalizes its classical counterpart by the existence of some incompatibility constraints
limiting the assignment of tasks to processing units within groups of mutually exclusive tasks. The groups are defined for
each processing unit and the constraints allow at most one task from each group to be assigned to the corresponding processing
unit. The processing units can normally process a certain number of tasks without any cost; this capacity can be extended,
however, at some extra marginal cost that is non-decreasing with the number of additional tasks. Each task has to be assigned
to exactly one processing unit and has some preference for the assignment; it is expressed for each pair ‘task-processing
unit’ by a dissatisfaction degree. The quality of feasible assignments is evaluated by three criteria: g
1-the maximum dissatisfaction of tasks, g
2-the total dissatisfaction of tasks, g
3-the total cost of processing units. If there is no feasible assignment, tasks and processing units creating a blocking configuration
are identified and all actions of unblocking are proposed. Formal properties of blocking configurations and unblocking actions
are proven, and an interactive procedure for exploring the set of non-dominated assignments is described together with illustrative
examples processed by special software. |
| |
Keywords: | Assignment problem Multi-criteria combinatorial optimization Incompatibility constraints Blocking configuration Actions of unblocking Non-dominated assignments Interactive exploration |
本文献已被 SpringerLink 等数据库收录! |
|