Simple k-crashing Plan with a Good Approximation Ratio

A project is considered as an activity-on-edge network (AOE network, which is a directed acyclic graph) 𝑁 , 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 𝑁. It is known that job 𝑗 𝑖 in normal speed would take 𝑏 𝑖 days to be finished after it is started, and hence the (normal) duration of the project 𝑁 , denoted by 𝑑 (𝑁), is determined, which equals the length of the critical path (namely, the longest path) of 𝑁. 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 𝑗 𝑖 has a lower bound due to technological limits-it requires at least 𝑎 𝑖 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 𝑐 𝑖 (slope), so that shortening 𝑗 𝑖 by 𝑑 (0 ≤ 𝑑 ≤ 𝑏 𝑖-𝑎 𝑖) days costs 𝑐 𝑖 • 𝑑 resources. Given project 𝑁 and an integer 𝑘 ≥ 1, the 𝑘-crashing problem asks the minimum cost to speed up the project by 𝑘 days. In this paper, we present a simple solution with the approximation ratio 1 1 +. .. + 1 𝑘. 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.