Approximation Alogrithms In Two New Scheduling Problem

This thesis contains two parts. In part one, a batch processing system is considered. The processing time and release date of job i are Pi and ri respectively. At the same time there are at most B(constant) jobs can be prosessed simultaneously, in which the processing time of a batch is the longest processing time among jobs in the batch. Jobs are executed non-preemptively. Our objective is to assign jobs to batches and determine the sequence so as to minimize the total completion time. In this paper , we design a PTAS for the case of identical parallel batch matchines with batch capacity and the number of machines both being constant. The objective is to minimize the total completion time on identical parellel batch machines .In part two, the problem of two-stage flexible flowshop with only one machine on the first machine center having limited machine availabity is proposed, under the assumption that the unavailable time intervals are known in advance . The objective function is to minimize the makespan on flexible flowshop. Some heuristics for the problem are presented and their performance guarantees are analyzed .Part one The PTAS for the Problem of Pm|rj, B| CjThe scheduling problem on identicall parallel batch machines with jobs having release times is firstly delivered. A PTAS is designed for the problem when the batch capacity and the number of machines are both constant.1. Definition and AssumptionDefinitionl+O( )cost: Each transformation potentially increases the objective function value by 1 + O( ) ,we shall say it produces 1 + O( ) cost.Polynomial-time Approximation Schemes(PTAS): A PTAS is a family of algorithm {A | > 0} such that for any fixed > 0, A runs in time polynomial in the length of the input and gets a solution with an objective value which is at most 1 + e times of the optimum .AssumptionsJobs are grouped into some batches. It is possible to view all the jobs in the same batch as a single aggregate job, with a process time which is equal to the processing time of the longest job in the batch. The release time of the batch is defined as the largest one of release times of all jobs in the batch.Once a batch is processed, it cannot be interrupted and other jobs cannot be introduced into the batch, obviously, the jobs in a batch have the same completion time.2.Polynomial-time Approximation Schemes(PTAS)Lemma 1 With 1 + cost, we can assume that all processing times and release dates are integer times of 1 + .Defintion We say that a job is small with repect to an interval Ix if its processing time Pj < Ix, otherwise large .Lemma 2 With 1 + ?cost, we can enforce rj Pj for all jobs j. Lemma 3 For any 1 i L,it follows thatTheorem 1 l\ can be solved with a PTAS by the algorithm Rg.Lemma 4 If all the jobs are small with respect to their released intervals ,then the RB algorithm is a (1 + -approximation in time n log n) Algorithm {A}Step 1 :Compute I from I .Step 2 -.Run RB for the instance /i, output a solution Si.Step 3 :Schedule the jobs for I by the ordering of siTheorem 2 the algorithm {A*} is a PTAS to / in time nlogn) if all jobs are small with respect to the intervals in which they arereleased.Lemma 5 (1) Each job crosses at most S = [logi+c ] intervals.(2) With 1 + e cost, we restrict attention to schedules in whichno small job crosses an interval.Defintion 2 A batch is said to be large if it contains at least one large job.Theorem 3 There is a (1 +3e)-optimal batch processing in which for each job j, Sj > min{-,}, where Sj denotes the starting time of job j.Algorithm {A}Step 1 :Run RB for the problem I1 untill at most jobs are left.Step 2 rSequence the batches in B in the order of batches output by Stepl and revert the modified release dates of the left jobs.Step 3 : Enumerate all possible batch sequence of the remainmes jobs to find the best one .Theorem 4 The algorithm A is a PTAS to I in time nlogn+ ( )( ) if B and m are both cons...