| In recent years, scheduling problem has attracted a great attention because of itsdeep background in the real world and bright future in various applicationenvironments. The classical scheduling problem usually assumes that the machinesare available simultaneously at all time. However, machines also need maintenanceduring the processing period, which leads to the machines are not available at all time.So many people considered the scheduling problems with a fixed non-availabilityinterval on machines. At the same time, we also consider the problem when every jobhas a delivery time, the reason for the problem is that in the large set jobs ofscheduling problems, we have to send the jobs to the consumers after their processing.So we not only consider the jobs’processing time but also consider the delivery time,so that the scheduling problems have more practical significance.This paper focuses on scheduling a set of jobs on parallel machines which has anon-availability constraint. There are four parts in this paper. In chapter 1, weintroduce the definition, expression and classification of the scheduling, as well as thenon-available constraint on machines and the job’s delivery time. In chapter 2, weconsider the problem of two parallel machines where one has a fixed non-availabilityconstraint interval and the other is available at all time. During the processing of thejobs, preemption is not allowed, the objective is to minimize the makespan. We firstgive some conclusions and use diagram to illustrate the dynamic programmingapproach, also a fully polynomial-time approximation scheme ( FPTAS ) is proposedand its time complexity is given to deal with the problem. In chapter 3, we mainlydiscuss the problem where one machine has a fixed non-availability interval and thejobs have delivery times after their processing. The objective is to minimize the timeby which all jobs have been delivered, we also give a fully polynomial-timeapproximation scheme and its time complexity for this problem. Finally we end the paper with a summery of the two problems. |
