Scheduling Relate With Due Dates

In this paper, we study some multi-processor scheduling problems relate to due dates. In chapterl, we introduce basic concepts about scheduling, the worst-case ratio analysis of approximation algorithms, stochastic scheduling problem and classes of stochastic scheduling policies.In chapter 2 we study two parallel machines scheduling to maximize non-delay jobs. The problem is NP-hard for it contains a sub problem equivalent to partition problem. Anapproximation algorithm A2-1 with absolute performance ratio 3/4 is proposed and the asymptotic performance ratio of A2-1 applied to the problem in which machines require preparetimes is 2/3 . Another problem is two parallel machines scheduling to maximize the number ofjust in time jobs. For this problem we give a polynomial time optional algorithm in the case early penalty is larger or equal to late penalty, and it is proofed to be NP-had when early penalty is less than late penalty.In chapter 3 we construct two approximation algorithms which applying bin packing algorithms for scheduling problems, one is FF(First Fit) algorithm used in parallel machinescheduling problem Pm//dJ = d/n which has a lower bound of asymptoticworst-case performance ratio, another problem is scheduling independentparallel tasks in parallel identical machine systems to minimize the makespan, we use strip packing method for it and give an approximation algorithm with asymptotic performance ratio no more than 1.6.In chapter 4 we study single machine scheduling problem with assignable due dates to maximize the number of non-delay jobs, an optional polynomial algorithm is proposed for the preemptive model, for non-preemptive model, we proofed that there is no algorithm withcompetitive ratio larger than zero. For preemption-restart model, we give a 1/2 -competitivealgorithm.In chapter 5, we study two- machine overload real-time systems online problem to maximize the sum of processing times of non-delay jobs. We presented a modified algorithm NSR and showthat the competitive ratio of NSR is 2/5 .In chapter 6 we study stochastic scheduling problems. We presented a series of heuristic algorithms Ga(0