Multi-criteria assignment problem with incompatibility and capacity constraints

Bernard Roy () and Roman Słowiński ()

Annals of Operations Research, 2006, vol. 147, issue 1, 287-316

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. Copyright Springer Science + Business Media, LLC 2006

Keywords: Assignment problem; Multi-criteria combinatorial optimization; Incompatibility constraints; Blocking configuration; Actions of unblocking; Non-dominated assignments; Interactive exploration (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-006-0070-3 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:147:y:2006:i:1:p:287-316:10.1007/s10479-006-0070-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-006-0070-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().