IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v34y2017i2d10.1007_s10878-016-0097-6.html
   My bibliography  Save this article

Task assignment in tree-like hierarchical structures

Author

Listed:
  • Cem Evrendilek

    (Izmir University of Economics)

  • Ismail Hakki Toroslu

    (Middle East Technical University)

  • Seyedsasan Hashemikhabir

    (Middle East Technical University)

Abstract

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.

Suggested Citation

  • Cem Evrendilek & Ismail Hakki Toroslu & Seyedsasan Hashemikhabir, 2017. "Task assignment in tree-like hierarchical structures," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 631-655, August.
    • Handle: RePEc:spr:jcomop:v:34:y:2017:i:2:d:10.1007_s10878-016-0097-6
    DOI: 10.1007/s10878-016-0097-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-016-0097-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-016-0097-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Walteros, Jose L. & Vogiatzis, Chrysafis & Pasiliao, Eduardo L. & Pardalos, Panos M., 2014. "Integer programming models for the multidimensional assignment problem with star costs," European Journal of Operational Research, Elsevier, vol. 235(3), pages 553-568.
    2. Han-Lin Li & Yao-Huei Huang & Shu-Cherng Fang, 2013. "A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment Problems," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 643-653, November.
    3. Chase Rainwater & Joseph Geunes & H. Edwin Romeijn, 2014. "Resource-Constrained Assignment Problems with Shared Resource Consumption and Flexible Demand," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 290-302, May.
    4. Armstrong, Ronald D. & Jin, Zhiying, 1995. "On solving a variation of the assignment problem," European Journal of Operational Research, Elsevier, vol. 87(1), pages 142-147, November.
    5. Ivan Contreras & Juan A. Díaz & Elena Fernández, 2011. "Branch and Price for Large-Scale Capacitated Hub Location Problems with Single Assignment," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 41-55, February.
    6. Geetha, S. & Nair, K. P. K., 1993. "A variation of the assignment problem," European Journal of Operational Research, Elsevier, vol. 68(3), pages 422-426, August.
    7. E. de Klerk & R. Sotirov & U. Truetsch, 2015. "A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 378-391, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. James F. Campbell & Morton E. O'Kelly, 2012. "Twenty-Five Years of Hub Location Research," Transportation Science, INFORMS, vol. 46(2), pages 153-169, May.
    2. Dhyani, Sneha & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2019. "Alternate Second Order Conic Programming Reformulations for Hub Location with Capacity Selection under Demand," IIMA Working Papers WP 2018-12-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    3. Roni, Md.S. & Eksioglu, Sandra D. & Searcy, Erin & Jha, Krishna, 2014. "A supply chain network design model for biomass co-firing in coal-fired power plants," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 115-134.
    4. Samuel Deleplanque & Martine Labbé & Diego Ponce & Justo Puerto, 2020. "A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 582-599, July.
    5. Sneha Dhyani Bhatt & Sachin Jayaswal & Ankur Sinha & Navneet Vidyarthi, 2021. "Alternate second order conic program reformulations for hub location under stochastic demand and congestion," Annals of Operations Research, Springer, vol. 304(1), pages 481-527, September.
    6. Pentico, David W., 2007. "Assignment problems: A golden anniversary survey," European Journal of Operational Research, Elsevier, vol. 176(2), pages 774-793, January.
    7. Li, Han-Lin & Fang, Shu-Cherng & Huang, Yao-Huei & Nie, Tiantian, 2016. "An enhanced logarithmic method for signomial programming with discrete variables," European Journal of Operational Research, Elsevier, vol. 255(3), pages 922-934.
    8. Meltem Peker & Bahar Y. Kara & James F. Campbell & Sibel A. Alumur, 2016. "Spatial Analysis of Single Allocation Hub Location Problems," Networks and Spatial Economics, Springer, vol. 16(4), pages 1075-1101, December.
    9. Alibeyg, Armaghan & Contreras, Ivan & Fernández, Elena, 2018. "Exact solution of hub network design problems with profits," European Journal of Operational Research, Elsevier, vol. 266(1), pages 57-71.
    10. Martello, Silvano & Pinto Paixão, José M., 2012. "A look at the past and present of optimization – An editorial," European Journal of Operational Research, Elsevier, vol. 219(3), pages 638-640.
    11. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R, 2017. "On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization," Annals of Operations Research, Springer, vol. 258(2), pages 301-346, November.
    12. Ivan Contreras & Jean-François Cordeau & Gilbert Laporte, 2011. "Benders Decomposition for Large-Scale Uncapacitated Hub Location," Operations Research, INFORMS, vol. 59(6), pages 1477-1490, December.
    13. Han-Lin Li & Yao-Huei Huang & Shu-Cherng Fang, 2017. "Linear Reformulation of Polynomial Discrete Programming for Fast Computation," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 108-122, February.
    14. Armstrong, Ronald D. & Jin, Zhiying, 1995. "On solving a variation of the assignment problem," European Journal of Operational Research, Elsevier, vol. 87(1), pages 142-147, November.
    15. P. Senthil Kumar, 2020. "Developing a New Approach to Solve Solid Assignment Problems Under Intuitionistic Fuzzy Environment," International Journal of Fuzzy System Applications (IJFSA), IGI Global, vol. 9(1), pages 1-34, January.
    16. Hu, Lu & Zhu, Juan Xiu & Wang, Yuan & Lee, Loo Hay, 2018. "Joint design of fleet size, hub locations, and hub capacities for third-party logistics networks with road congestion constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 568-588.
    17. Nader Azizi & Navneet Vidyarthi & Satyaveer S. Chauhan, 2018. "Modelling and analysis of hub-and-spoke networks under stochastic demand and congestion," Annals of Operations Research, Springer, vol. 264(1), pages 1-40, May.
    18. Alumur, Sibel A. & Campbell, James F. & Contreras, Ivan & Kara, Bahar Y. & Marianov, Vladimir & O’Kelly, Morton E., 2021. "Perspectives on modeling hub location problems," European Journal of Operational Research, Elsevier, vol. 291(1), pages 1-17.
    19. Qingyun Tian & Yun Hui Lin & David Z. W. Wang, 2021. "Autonomous and conventional bus fleet optimization for fixed-route operations considering demand uncertainty," Transportation, Springer, vol. 48(5), pages 2735-2763, October.
    20. Zetina, Carlos Armando & Contreras, Ivan & Cordeau, Jean-François & Nikbakhsh, Ehsan, 2017. "Robust uncapacitated hub location," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 393-410.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:34:y:2017:i:2:d:10.1007_s10878-016-0097-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.