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.
This paper focuses on scheduling a set of jobs on a single machine on which a maintenance task has to be performed under the non-resumable scenario. The objective is to minimize the total weighted completion time. The machine is unavailable during a fixed interval. This type of problems has been studied in the literature under various criteria (Gharbi and Haouari, 2005 and Lee and Chen, 2000). Given the aim of our study, we present a brief overview of previous works related to this subject.
The simplest case, that is minimizing total completion time with a single fixed non-availability interval (denoted 1,h1∥∑Ci1,h1∥∑Ci), was proved to be NP-Hard by Adiri et al., 1989 and Lee and Liman, 1992. Several references studied the worst-case performance of heuristic methods (a sample of these papers includes Adiri et al., 1989, Kacem, 2007, Lee and Liman, 1992, Sadfi et al., 2005, He et al., 2006 and Breit, 2006).
Recently, numerous references considered the problem of simultaneously scheduling jobs and maintenance tasks on a single machine (see for example Qi, Chen, & Tu (1999) and Qi (2007) who considered the minimization of the sum of completion times, or Chen (2006) who proposed a branch-and-bound algorithm for solving a similar problem). Others numerous references addressed the shop scheduling problems (parallel machine, flow shop and job shop problems) and they proposed exact and heuristic methods (Aggoune, 2004, Aggoune and Portmann, 2006, Allaoui and Artiba, 2006, Allaoui et al., 2006, Kubzin and Strusevich, 2006, Lee, 1996, Lee, 2004, Lee and Chen, 2000, Lee and Liman, 1993, Mosheiov, 1994 and Schmidt, 2000).
In this paper, we considered the non-resumable version of the scheduling problem on a single machine with one availability constraint. We studied the criterion of the weighted sum of the completion times. No polynomial 2-approximation algorithm for this problem has been previously known. We proposed a 2-approximation algorithm with O(n2) time complexity. Such an approximation extends the one proposed by Wang et al. (2005) for the resumable scenario. In our future works, we hope to extend these results to other variants of this problem. The development of better approximation algorithms is also a challenging subject.
