Computational performances of a simple interchange heuristic for a scheduling problem with an availability constraint

• We address a scheduling problem subject to an unavailability constraint.
• We study an existing interchange heuristic to minimize the total-flow time.
• We improve the theoretical error bound of this heuristic and prove its tightness.
• We provide computational experiments of this heuristic.
• These experiments demonstrate the relevance of the algorithm for applications.

This paper deals with a scheduling problem on a single machine with an availability constraint. The problem is known to be NP-complete and admits several approximation algorithms. In this paper we study the approximation scheme described in He et al. [Y. He, W. Zhong, H. Gu, Improved algorithms for two single machine scheduling problems, Theoretical Computer Science 363 (2006) 257–265]. We provide the computation of an improved relative error of this heuristic, as well as a proof that this new bound is tight. We also present some computational experiments to test this heuristic on random instances. These experiments include an implementation of the fully-polynomial time approximation scheme given in Kacem and Ridha Mahjoub [I. Kacem, A. Ridha Mahjoub, Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers and Industrial Engineering 56 (2009) 1708–1712].