An O(n2) algorithm for a controllable machine scheduling problem

A single-machine scheduling problem with controllable processing times is discussed in this paper. For some jobs, the processing time can be crashed up to u units of time with the additional cost c per unit of time crashed. The object is to find an optimal processing sequence as well as crash activities to minimize total costs of completion and crash. This problem is shown to be polynomially solvable, and an O(n²) algorithm is given together with the theoretical proof.