Task assignment in tree-like hierarchical structures


Creative Commons License

EVRENDİLEK C., TOROSLU İ. H. , Hashemikhabir S.

JOURNAL OF COMBINATORIAL OPTIMIZATION, cilt.34, ss.631-655, 2017 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 34 Konu: 2
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1007/s10878-016-0097-6
  • Dergi Adı: JOURNAL OF COMBINATORIAL OPTIMIZATION
  • Sayfa Sayıları: ss.631-655

Ö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.