Simple <i>k</i>-Crashing Plan with a Good Approximation Ratio
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 <i>N</i> (which is a directed acyclic graph). To speed up the project (i.e., reduce the duration), the manager can crash a few jobs (n...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-07-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/14/2234 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 <i>N</i> (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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mstyle scriptlevel="0" displaystyle="true"><mfrac><mn>1</mn><mn>1</mn></mfrac></mstyle><mo>+</mo><mo>…</mo><mo>+</mo><mstyle scriptlevel="0" displaystyle="true"><mfrac><mn>1</mn><mi>k</mi></mfrac></mstyle></mrow></semantics></math></inline-formula> for this <i>k</i>-crashing problem. |
|---|---|
| ISSN: | 2227-7390 |