Task assignment in tree-like hierarchical structures
JOURNAL OF COMBINATORIAL OPTIMIZATION, cilt.34, sa.2, ss.631-655, 2017 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 34 Sayı: 2
- Basım Tarihi: 2017
- Doi Numarası: 10.1007/s10878-016-0097-6
- Dergi Adı: JOURNAL OF COMBINATORIAL OPTIMIZATION
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.631-655
- Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
- Orta Doğu Teknik Üniversitesi Adresli: Evet
Özet
Many large organizations, such as corporations, are hierarchical by nature. In hierarchical organizations, each entity, except the root, is a sub-part of another entity. In this paper, we study the task assignment problem to the entities of a tree-like hierarchical organization. The inherent tree structure introduces an interesting and challenging constraint to the standard assignment problem. Given a tree rooted at a designated node, a set of tasks, and a real-valued function denoting the weight of assigning a node to a task, the Maximum Weight Tree Matching (MWTM) problem aims at finding a maximum weight matching in such a way that no tasks are left unassigned, and none of the ancestors of an already assigned node is allowed to engage in an assignment. When a task is assigned to an entity in a hierarchical organization, the whole entity including its children becomes responsible from the execution of that particular task. In other words, if an entity has been assigned to a task, neither its descendants nor its ancestors can be assigned to any task. In the paper, we formally introduce MWTM, and prove its NP-hardness. We also propose and experimentally validate an effective heuristic solution based on iterative rounding of a linear programming relaxation for MWTM.