Scheduling With Machine Has Non-availability Constraint And Jobs Has Delivery Times

In this paper,we consider the non-resumable case of the machine scheduling problem with a non-availability constraint interval,which is fixed and known in advance .And the job have a delivery time has been delivered to customers after completion.First,we consider the problem of two parallel machines where one has a fixed non-availability constraint interval and the other available all time. the objective is to minimize the time by which all jobs have been delivered.The problem is NP-hard.We propose a polynomial approximation algorithm with a worst-case performance ratio of 8/5, and show that the bound is tight. At the same time we present a dynamic programming method and mixed integer programming model to solve this problem.Secondly,we consider a single-machine problem with an non-availability constraint. The objective is to minimize the largest weighted time by which all jobs have been delivered. this problem is NP-hard too.We solved the problem using dynamic programming method and mixed integer programming model. We also propose two polynomial approximation algorithms under the case of q_i=q_o with a worst-case performance ratio of 2 and 1+ε, respective.Thirdly,we also consider a single-machine problem with an non-availability constraint. The objective is to minimize the weighted sum of time by all jobs have been delivered. this problem is also NP-hard .We solving it with dynamic programming method and mixed integer programming model.