Simple k -Crashing Plan with a Good Approximation Ratio

Ruixi Luo, Kai Jin () and Zelin Ye
Additional contact information
Ruixi Luo: School of Intelligent Systems Engineering, Shenzhen Campus of Sun Yat-sen University, No. 66, Gongchang Road, Guangming District, Shenzhen 518107, China
Kai Jin: School of Intelligent Systems Engineering, Shenzhen Campus of Sun Yat-sen University, No. 66, Gongchang Road, Guangming District, Shenzhen 518107, China
Zelin Ye: School of Intelligent Systems Engineering, Shenzhen Campus of Sun Yat-sen University, No. 66, Gongchang Road, Guangming District, Shenzhen 518107, China

Mathematics, 2025, vol. 13, issue 14, 1-20

Abstract: In project management, a project is typically described as an activity-on-edge network, where each activity/job is represented as an edge of some network N (which is a directed acyclic graph). To speed up the project (i.e., reduce the duration), the manager can crash a few jobs (namely, reduce the length of the corresponding edges) by investing extra resources into those jobs. Greedily and repeatedly choosing the cheapest solution to crash the project by one unit is the simplest way to achieve the crashing goal and has been implemented countless times throughout the history. However, the algorithm does not guarantee an optimum solution and analysis of it is limited. Through theoretical analysis, we prove that the above algorithm has an approximation ratio upper bound of 1 1 + … + 1 k for this k -crashing problem.

Keywords: project duration; network optimization; greedy algorithm; maximum flow; critical path (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/14/2234/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/14/2234/ (text/html)

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:gam:jmathe:v:13:y:2025:i:14:p:2234-:d:1698367

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().