An alternate approach to solve two-level priority based assignment problem

Fanrong Xie (), Anuj Sharma () and Zuoan Li ()
Additional contact information
Fanrong Xie: Sichuan University of Science and Engineering
Anuj Sharma: Panjab University
Zuoan Li: Sichuan University of Science and Engineering

Computational Optimization and Applications, 2022, vol. 81, issue 2, No 9, 613-656

Abstract: Abstract Two-level priority based assignment problem (2PBAP) is an important optimization problem due to the timely delivery requirement in project management. Only four methods with deficiency are available in the literature to solve 2PBAP. In this paper, 2PBAP is reduced to a series of finding the feasible flow in a network with lower and upper arc capacities, and consequently two iterative algorithms are developed to solve 2PBAP. It is proved that both iterative algorithms find the optimal solution to 2PBAP in a strongly polynomial time. Owing to having fully utilized the network flow structural characteristic inherent to 2PBAP, both iterative algorithms have the advantages such as easy implementation on computer, no memory overflow in implementation on computer for large scale instances, high computational efficiency, and easy extension to the priority based assignment problem with priority level more than two, and successfully overcome the deficiency of existing approaches. Computational experiments validate that in terms of computational time, one of our proposed iterative algorithms has higher efficiency than the other, and rivals the existing best approach.

Keywords: Combinatorial optimization; Assignment problem; Iterative algorithm; Maximum flow; Network with lower and upper arc capacities (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-021-00340-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:coopap:v:81:y:2022:i:2:d:10.1007_s10589-021-00340-0

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

DOI: 10.1007/s10589-021-00340-0

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().