Algorithm Design And Performance Analysis For Some New Parallel Machine Scheduling And Routing Problems

In.this thesis,we consider some new parallel machine scheduling and routing prob-lems,including the restricted assignment problem,parallel machine scheduling with a buffer,a repairman problem visiting all the edges and the reclaimer scheduling prob-lem.We analyze the time complexity of these problems,design algorithms,study the performance of those algorithms and conduct numerical simulations for some algorithms.In Chapter 1,we introduce the background of combinatorial optimization and pro-vide the theoretical knowledge related to this thesis,including the complexity of the algorithm,NP complete theory,linear programming rounding technique and matching.Then the definitions and notations of scheduling and routing problems are introduced,and literature review is given at last.In Chapter 2,we consider some special cases of the problems of minimizing makespan on unrelated machines.Given,m machines and n jobs,job Jj can only be processed on a subset of machines Mj,and the process time is pj.We give a new and simple algorithm for the graph balancing problem with the ratio of 1.883.We consider the case in which each job can be processed on an interval of machines,and there are only two kinds of jobs in which the size of the big jobs is larger than half of the target value.We prove that this case can be solved in polynomial time.Furthermore,we also present a PTAS for intervals of the same length for each job.Then we provide some negative results:If the restricted version in which each job can only be placed on three machines has(2-?)-approximation algorithm,then R||Cmax has(2-?)-approximation algorithm.If uniformly related graph balancing problem has(2-?)-approximation algorithm,then unrelated graph balancing problem has(2-?)-approximation algorithm.In Chpater 3,a parallel machine scheduling problem with a buffer to minimize total completion time is studied.The sequence of the jobs is fixed beforehand,so we can only schedule the jobs one by one without a buffer.If there exists a buffer,each job will enter a buffer before being scheduled,and we can select one job within the buffer arbitrarily.The buffer has the capability to change the sequence to some extent.Firstly we give some negative instances to show that the classic scheduling rules will not get optimal solutions.Then given the number of machines and the size of buffer,we develop a dynamic programming in polynomial time.Moreover,if the number of machines is not known,we prove that it becomes NP-hard in strong sense even if the size of the buffer is only 1 for the weighted case.In Chapter 4,given a graph,a repairman wants to visit all the edges at least once from the starting point,such that the average visiting time of the edges is minimized.Here we assume that each edge is composed of points,and the objective function becomes minimizing the average visiting time of all the points.This problem is different with the well-known Chinese postman problem and travelling salesman problem,and it is a special case of travelling repairman problem.We show that the problem is NP-hard for the undirected as well as directed graphs.We then give a(?)-approximation algorithm for undirected graphs and a 4/3-approximation algorithm if the undirected graph is two connected.In Chapter 5,we consider a reclaimer scheduling problem in the quay in which multiple reclaimer machines will collect bulk material from the stockpiles.Each machine occupies one straight track,and the stockpiles are located on both side of the tracks.Thus the machines need to travel to the locations of the stockpiles and then reclaim the bulk material in such a way that the time used is minimized.When reclaimers are allowed to work on the same stockpile simultaneously,a fully polynomial time approximation scheme is designed.Moreover,we present a 2-approximation algorithm in the case that any stockpile can be handled by at most one reclaimer at a time.When the number of reclaimers is two,we give a 3/2-approximation algorithm.Numerical experiments show that the algorithms performs much better than our worst case analysis guarantees.In Chapter 6,our research results are concluded and several topics are presented for future research.