Exponential inapproximability and FPTAS for scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to one or more identical machines with the constraint that the machines may be unavailable in some specified time intervals. The objective is to find a schedule that minimizes the total weighted completion time. We consider both non-resumable and resumable schedules.Our first contributions concern approximability. For both resumable problem and non-resumable problem, we show that they cannot be approximated within an exponential factor by any polynomial time algorithm for multiple machines where each of them has an unavailable interval, even if the weight of each job equals to its processing time. Additionally, the non-resumable problem is also exponentially inapproximable for a single machine with two or more unavailable intervals.Then we develop the first FPTASs for the problems with a single unavailable interval among all machines. The running time is for the non-resumable problem, and for the resumable problem, where w is the product of the total weight and the total processing time of all jobs, c is the number of machines that are always available and d=6c+12. Thus our results give a clear boundary delineating the inapproximable cases and approximable cases. When there is a single machine and w=O(nlognO(1)), our algorithms greatly improve the current results.Note that instead of conventional ways of sequentially processing the jobs, our fast schemes process jobs in a divide-and-conquer fashion, which greatly reduces the running time. This may give some insight for some other related problems.