Task assignment in tree-like hierarchical structures

Download

index.pdf

Date

2017-08-01

Author

EVRENDİLEK, CEM
Toroslu, İsmail Hakkı
Hashemikhabir, Seyedsasan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

34
views

23
downloads

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.

Subject Keywords

Task assignment, Integer programming, Linear programming relaxation, Heuristics, NP-hardness

URI

https://hdl.handle.net/11511/48092

Journal

JOURNAL OF COMBINATORIAL OPTIMIZATION

DOI

https://doi.org/10.1007/s10878-016-0097-6

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Corporate governance compliance : a study of the publicly traded companies on Istanbul stock exchange Erensoy, Müjde; Muğan, Fatma Naciye Can; Department of Business Administration (2011) In the contemporary global world, corporate governance is one of the most frequently referred business term. This study examines the corporate governance compliance reports submitted to Capital Markets Board (CMB) by the publicly traded companies on İstanbul Stock Exchange (ISE). In the analysis, relation among corporate governance compliance and size and ownership structure is investigated. Corporate governance compliance scores of the companies are obtained from Corporate Governance Index constructed base...
Organizational learning assessment in software development organizations Chouseinoglou, Oumout; Bilgen, Semih; Yöndem, Meltem Turhan; Department of Information Systems (2012) Knowledge is one of the most important assets of an organization that directly affects business success, and its importance increases for organizations that use knowledge-intensive processes such as the software development industry. In an industry in which technological developments are rapid, in order to keep up with the continuously increasing competition and to obtain competitive advantage the software organizations need to obtain the correct knowledge, use it efficiently and pass it to future projects ...
Technology development centers in Turkey Akçomak, İbrahim Semih; Taymaz, Erol; Department of Economics (2003) It is widely accepted that small and new firms are important in creating income and employment. Their flexible structure enables them to adapt quickly to changes in economic environment and technology. The main purpose of this thesis is to evaluate whether the Technology Development Centers (TEKMERs) established by the Small and Medium Size Industry Development Organization (KOSGEB) in Turkey encourage new firm creation in high-technology sectors and boost the performance of small and new firms both in term...
Developing Process Definition for Financial and Physical Resource Management Process in Government Domain Gökalp, Ebru (2016-06-10) Public Financial and Physical Resource Management (PFPRM) is becoming a core competency critical to a government organization's competitive advantage. Recent studies have shown that organizations with established PFPRM are able to generate millions of dollars in additional savings and have a distinct competitive advantage. Our literature review showed that there is also a lack of a guideline for process capability determination and improvement of PFPRM. On the other hand, after observing benefits in softwar...
Is Individualism a Predictor of Social Capital in Business Incubators? Aşcıgil, Semra Feriha (2013-06-01) This paper examines whether entrepreneurs’ individualism is related to their perceptions of social capital within a business incubator of which their company is a tenant. Social capital is a resource derived from the content and structure of social relations among incubator tenants. Questionnaire data from managers of tenant companies of five incubators established by the State Privatization Office of the Turkish Republic were analyzed with regression. Individualism had a positive relationship with percepti...

Citation Formats

C. EVRENDİLEK, İ. H. Toroslu, and S. Hashemikhabir, “Task assignment in tree-like hierarchical structures,” JOURNAL OF COMBINATORIAL OPTIMIZATION, pp. 631–655, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/48092.