Fast approximation algorithms to minimize a special weighted flow‐time criterion on a single machine with a non‐availability interval and release dates

This paper is the first attempt to successfully design efficient approximation algorithms for the single‐machine weighted flow‐time minimization problem when jobs have different release dates and weights equal to their processing times under the assumption that one job is fixed (i.e., the machine is unavailable during a fixed interval corresponding to the fixed job). Our work is motivated by an interesting algorithmic application to the generation of valid inequalities in a branch‐and‐cut method. Our analysis shows that the trivial FIFO sequence can lead to an arbitrary large worst‐case performance bound. Hence, we modify this sequence so that a new 2‐approximation solution can be obtained for every instance and we prove the tightness of this bound. Then, we propose a fully polynomial‐time approximation algorithm with efficient running time for the considered problem. Especially, the complexity of our algorithm is strongly polynomial.