Abstract: In this article, we consider a single-machine scheduling problem with one unavailability period, with the aim of minimizing the weighted sum of the completion times. We propose three exact methods for solving such a problem: a branch-and-bound method based on new properties and lower bounds, a mixed integer programming model, and a dynamic programming method. These methods were coded and tested on randomly generated instances, and their performances were analyzed. Our numerical experiments show that the branch-and-bound method and the dynamic programming method are complementary. Using these approaches, we are able to solve problems with up to 3000 jobs within a reasonable computation time.

Abstract: In this article, we consider the single-machine scheduling problem with one availability constraint. We aim to minimize the weighted sum of completion times. We propose a branch-and-bound algorithm based on a set of improved lower bounds and heuristics. The numerical experiments show the effectiveness of the proposed method. The improved algorithm is able to solve instances of 6000 jobs in a reasonable amount of computation time.

Abstract: In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the weighted sum of completion times. No polynomial 2-approximation algorithm for this problem has been previously known. We propose a 2-approximation algorithm with O(n2) time complexity where n is the number of jobs. We show that this bound is tight. The obtained result outperforms all the previous polynomial approximation algorithms for this problem.

Abstract: In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the makespan when every job has a positive tail. We propose a polynomial approximation algorithm with a worst-case performance ratio of 3/2 for this problem. We show that this bound is tight. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm) by exploiting the well-known approach of Ibarra and Kim (J. ACM 22:463–468, 1975). Such an FPTAS is strongly polynomial. The obtained results outperform the previous polynomial approximation algorithms for this problem.

Abstract: In this article, we consider the single machine scheduling problem with one planned setup period, with the aim of minimizing the weighted sum of the completion times. We study the WSPT and MWSPT heuristics and we show that the worst-case performance ratio is 3 for the two heuristics in some cases and it is unbounded otherwise. We also show that these worst-case performance ratios are tight.