@inproceedings{10.5555/3635637.3663162,
author = {Luo, Ruixi and Jin, Kai and Ye, Zelin},
title = {Simple k-crashing Plan with a Good Approximation Ratio},
year = {2024},
isbn = {9798400704864},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
address = {Richland, SC},
abstract = {A project is considered as an activity-on-edge network (AOE network, which is a directed acyclic graph) N, where each activity / job of the project is an edge. Some jobs must be finished before others can be started, as described by the topology structure of N. It is known that job ji in normal speed would take bi days to be finished after it is started, and hence the (normal) duration of the project N, denoted by d(N), is determined, which equals the length of the critical path (namely, the longest path) of N.To speed up the project, the manager can crash a few jobs (namely, reduce the length of the corresponding edges) by investing extra resources into that job. However, the time for completing ji has a lower bound due to technological limits - it requires at least ai days to be completed. Following the convention, assume that the duration of a job has a linear relation with the extra resources put into this job; equivalently, there is a parameter ci (slope), so that shortening ji by d(0 ≤ d ≤ bi-ai) days costs ci⋅ d resources.Given project N and an integer k ≥ 1, the k-crashing problem asks the minimum cost to speed up the project by k days.In this paper, we present a simple solution with the approximation ratio 1 over 1 + … + 1 over k. For simplicity, we focus on the linear case throughout the paper, but our proofs are still correct for the convex case, where shortening an edge becomes more difficult after a previous shortening.},
booktitle = {Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems},
pages = {2366–2368},
numpages = {3},
keywords = {critical path, greedy algorithm, maximum flow, network optimization, project duration},
location = {Auckland, New Zealand},
series = {AAMAS '24}
}