Batching Scheduling Jobs Subject To Precedence Constraints

Scheduling problem is an important research field. Batching machine scheduling problem has its root in various application areas and has attracted a lot of attention recently. Many manufacturing systems contain batch processors. In the paper, we consider the problems of scheduling jobs subject to precedence constraints (a precedence relation J_i< J_j implies job J_i must be completed before job J_j beginning to be processed.) and release dates on a batching machine with the objective of minimizing makespan(i.e. the completion time of the last job when processed). Three chapters are included in this thesis.In the first chapter, some notations, definitions and background about the subject are introduced.In the second chapter, the problem where jobs with different release dates are under parallel chain-type(i.e. every job has at most one direct predecessor and at most one direct successor) is discussed. We consider the case with m chains one of which contains n jobs and the others contain a constant number of jobs, in addition, all jobs have different release dates. For this case we present a polynomial algorithm.In chapter 3, we consider the problem of scheduling the jobs subject to precedence constraints, different sizes and release dates on a batch processing machine with the objective of minimizing the makespan. It hasn't been widely studied in recent related work. We discuss the case where jobs have identicalprocessing time p and release dates r, = e + kjp for 1 < j < n, i.e.Sj,prec, rj = efcj = L^-J, e is a constant number and 0 < e < p — 1. We present two polynomial algorithms for the case where jobs have identical sizes and for the case where jobs with non-identical sizes can be split when processed. Based on the above algorithms, a 2-approximation algorithm is presented by putting the two parts of a split job into a new batch and processing. Furthermore, the algorithm can also be applied for other objective functions.In addition, with the help of Prof. Zhang, we also study Minimizing Cost Flow(MCF) problem and Location problem. We supplement several other cases in Buildup Algorithm provided in the monograph of the famous mathematician C.H.Papadimitriou. Chapter 4 includes the main results of our two published papers.