Scheduling On Single And Parallel Michines With Constraints

Three chapters are concluded in this thesis.In the first chapter, some notation, definitions and basic background information about the subject are introduced.In the second chapter, we address the problem of scheduling jobs on a single machine on which the total processing amount, including the processed jobs that have not been delivered and the processed part of job that is processing, can not excess a constant number K at any time. Two kinds function of the problems are considered: minimize the total of the delay jobs and minimize maximum tardiness.The problem 1,K|di| Ui is firstly considered in ?.1. Without loss of generality, we assume that pi di, and pi K, i = 1, 2, ... , n.For any Instance I of the problem 1,K|di| Ui, we define a pseudo-schedule such that schedule the jobs according to the order and assign each job with Ci di and Ci as near di as possible. In the following, let Ci be the starting time and Si the complete time of job pi in the pseudo-schedule(Notice: the starting time of some jobs may be negative in the pseudo-schedule) . Alg.1Step 1. Give these jobs J = (p1,p2, ... ,pn) a pseudo-schedule on single machine. Step 2. Examine each job in J from the last one. If there does not exist a job with di - Ci + pi> K or Si < 0, we obtain an optimal schedule. Otherwise, supposing pi is the first one of those jobs.Step 3. Let i = pi andTake a job such that h = max{i, i+1, ... , n}. If there are more than onejob reach the maximum, we will choose the job ph with the smallest index andput ph. behind all other jobs to be processed. Step 4. Translate pi(i = 1, 2, ... , h-1) backward(we assume the direction of thetime from zero to infinity as "backward", other as " forward" )to the greatestextent with , and let J = J \ {ph} then turn to Step 2.Let P(t1, t2) be the total processing amount from the time t1 to t2 on the machine.Definition 2.1 For any schedule , if the job pi meets P(Si, di) K and Si 0, we denote it feasible in , otherwise unfeasible.In the following we will analysis the characteristics of optimal schedule and feasible schedule for the problem Lemma 2.1 In arbitrary optimal schedule for the problem there must be a job to be delayed among {pi, ... ,pn}, if there is the first job Pi found in Alg.1.Lemma 2.2 Let {pi1, . . . ,pin} be a feasible schedule of J for the problem 1, K|di| Uj. If the job pij is feasible in {pi1, . . . ,pin}, the backward translation of all jobs in {pij, . . . ,pin} does not infect the feasibility of pij .Lemma 2.3 There exists an optimal schedule with the form (A,R), where All jobs in A can meet their due-dates and satisfies . All jobs in R are tardy.From Lemma 2.3 we conclude that for finding an optimal schedule we can restrict our attention to schedule of form (A, R) only.Let Gk = J \ {pk}(k = 1,2, ... ,n) and L(Gk) be the number of the jobs which can meet their due-dates in the optimal schedule for Gk. Suppose (Ak, Rk) is an optimal schedule for Gk, then L(Gk) = |Ak|.Difinition 2.2 Suppose J' J. Let ' be a scheduling for J' after (or before) a time t, we say ' is a partly feasible scheduling after (or before) a time t for J', if all jobs are feasible in ' . Futhermore, if all job can meet their due-dates in ', ' is a partly optimal scheduling.Lemma 2.4 L(Gh) L(Gk), k = i, i + 1, ... , n, where ph and pi are the jobs found in Alg.1.Theorem 2.1 For the problem l,.K|di| Ui, the Alg.l always delivers an optimal schedule.Next we considered the problem 1,K|di|Tmax.Firstly, we assume if a job is tardy, it would be deliver as soon as the job is completed. Without lose of generality, let pi K, i = 1,2, ... , n. Alg.2Step 1. Index all jobs such that Step 2. Let the starting time of p1 be S1 = max{d1 - K, 0}, the starting time of pi+1 be Si+1 = max{di+1 - K, C,}, i = 1,2, .. , n - 1, where Ci is the complete time of piFor proving that the Alg.2 can solve the problem optimally, we give two Lemmas in the following. From those, we can drew a conclusion that t...