Scheduling Problems With Unusable Intervals And Rejection Of Jobs

The classical scheduling assumes that machines are available at all times and all jobs have to be processed.However,these situations may not be true in real life,for example,the machine denoted by M may not be available due to preventive maintenance or a breakdown;the job denoted by Jj may be rejected when producers make a bigger profit on limited resources.On the basis of classical scheduling,we consider the single-machine scheduling problem and the two-machine permutation scheduling problem that there may be an unusable interval on machines and some jobs can be rejected.We consider the first problem denoted by (?),First-ly,we prove this problem is NP-hard by the property that partition problem is NP-hard.Secondly,we present a dynamic algorithm denoted by DP and analyze the complexity of DP.Specially,we provide a 3-approximation algorithm and a polynomial-time approximate scheme for this problem when the length of unusable interval denoted by t is restricted.And then we consider two-machine permutation scheduling problem as fol-lows:(?)and Firstly,we prove these problems are NP-hard.Secondly,we present a approximate algorithm denoted by M-SPT-LPT by improving the SPT-LPT when the length of unusable interval denoted by t is restricted.Thirdly,we prove M-SPT-LPT is a 2-approximation algorithm and 2 is tight for above problems.