| 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 studies the problem of scheduling n jobs on a single batching machine to minimize total weighted late work.Given a schedule, we can easily compute the completion time Cj of job Jj(j=1, … , n) and its late work Vj = min{7},pj}, where Tj = max{(Cj -dj, 0}. The late work Vj is the amount of processing performed on job Jj after its due date. If Vj = 0, the job Jj is early; if 0 < Vj < Pj, the job Jj is partially early; alternatively, if Vj - Pj, the job Jj is late. The objective is to find a processing order of jobs which minimizes the total weighted late work W We denote our problem as 1|B| nj=1 wjVj applying the notation in Graham et al.[13].Theorem 2.1 The problem 1|B| nj=1 wjVj is NP-complete.We will prove it by reduction from the well known PARTITION problem, which is described as following:Given a set G = {a1, 02, … , am] of m positive integers, is there a subset X of {1, 2, … , m} such thatGiven an instance of PARTITION, we construct our problem as follow:There are three tyes of jobs and a total of 2m+1 jobs. For each job Jj(j = 1, 2, … , m), let Pj = jm2A4 + a,j, Wj = aj/jm2A4, and dj = 1/2j(j + 1)m2A4 + A. For job m + j(j = 1,2, … ,m), let pm+j = jm2A4, wm+:j = A + 1, and dm+j = 1/2j(j + 1)m2A4 + A. Note that Jj and Jm+j have the same due date, for j -1,2, … , m. The last job, numbered 2m + 1, has a sufficient large positive weight M and its due date is 1/2m3(m +1)A4 + A and its processing time is f. for a sufficiently small e > 0.The times it takes to construct the instance is obviously polynomial.We show that the PARTITION problem has a solution if and only if there is a schedule for the corresponding instance of the total weighted late work withSuppose that the PARTITION problem has a solution X, let Y = X. Without loss of generality, we assume m X. Our scheduling is defined as following: First, each job Jj(j -1, … , m) is assigned to batch Bj if j X, and is assigned to batch Bj+1 if j Y. The jobs m + 1, … , 2m is assigned to batches B1, … , Bm respectively. The job with processing time is scheduled in a batch of only one job.We can caculate the total weighted late work of this shcdule contentsSuppose conversely that there is a schedule with Let X and Y denote the set of indices j(j = 1, … , m) for which j e and j Bj, respectively.In the third chapter, we discuss the problem of preemptively schedule on-line jobs on m parallel machines, which have nonsimultaneous machine available times ai. In such a setting, the jobs arrive one by one. Job Jj becomes known (with its existence and its processing time pj) only when job Jj-1 has already been scheduled. Job processing can be preemptive, i.e., the processing of any job can be interrupted and resumed later.First we give some notations:where r Lti: the load of the machine at step t (i.e., immediately after the ith job has been scheduled) OPTt: the current optimum makespan in step t (for the job set { J1; … , Jt}) LBt: the lower bound of the length in step tFor a set of jobs with processing times P1,…,pn, there are three straightforward lower bounds for the makespan of any preemptive schedule on m identical machines: maxSo we haveLB = max (3.2.1)The algorithm will schedule jobs in such a way that, at any step tAlgorithm:A new job Jt+1 (which arrives at time t + 1) is assigned as follows: Step 1 Compute the new lower bound LBi+1 according to (3.2.1) Step 2 Research the following reserved intervals. On machine Mm, the interval:, and on machine Mj(1 < i < m - 1), the intervalStep 3 To assign Jt+1, go from Im to I1, putting a part of the job, as large as possible in each interval, until all the job is assigned.After the assighment there will be some fully occupied intervals Il+1, … , Im, some empty intervals I1, … ,Il-1 and a partially or fully occupied inter...
|
PDF Full Text Request