Research On Scheduling Problems With The Feature Of Phased Job Processing

Scheduling problem is a classical problem in combinatorial optimization problems.This thesis mainly studies some scheduling problems with staged characteristics,which are widely used in practical production management.The core of this thesis is the design and analysis of approximation algorithm and(complete)polynomial time approximation scheme.This thesis is divided into six chapters.In the first chapter,some basic concepts related to scheduling problems are briefly introduced,and some recent research results of the scheduling problems with staged characteristics are introduced.In chapter 2,a two-machine flow shop scheduling problem with job no-wait and multi-task flexibility of the first machine is investigated by considering the minimization of makespan as criterion.In this problem,every job is divided into two stages,and it needs to be processed non-preemptively on each machines.The first operations of every jobs can only be processed on the first machine,and the second operations of every jobs can be processed on either two machines.We present a 1.615 approximation algorithm for this problem,which is better than the 13/8approximation algorithm we have know.In chapter 3,a two-machine flow shop scheduling problem with job process and job transportation is investigated.In this problem,every job is first processed on the two-machine flow shop,and then transported to the customer by one transport vehicle in batches.Each job occupies different size in the vehicle during transportation and the vehicle has limited capacity.The goal is minimize the time when the last job is transported to the customer.We constructs an approximate algorithm with the worst-case bound no more than(5/3+?),which is better than the 2 approximatio1 algorithm we have know.In chapter 4,a hybrid flow shop problem with the first stage of parallel machines and the second stage of dedicated machines is investigated.In this problem,every job has two operations,the first operation is processed on one of the parallel machines and then the second operation must be processed on a specified machine at stage two depending on job type.The objective is to minimize the maximum job completion time.We first propose a polynomial-time approximation algorithm with worst case ratio of 2 and then propose a polynomial time approximation scheme(PTAS).In chapter 5,the m parallel identical 2 and k stages job shops scheduling problems are investigated.In this problem,every job needs to be processed non-preemptively on any one of the job shop.The objective is to minimize the maximum job completion time.For the problem of the m parallel identical 2 stages job shops scheduling problems,we propose a fully polynomial time approximation scheme(FPTAS).For the problem of the m parallel identical k stages job shops scheduling problems,we propose a polynomial time approximation scheme(PTAS).In chapter 6,we give the summary and outlook of this thesis.