Two Scheduling Problems With Chain Precedence Constraints

Scheduling problem is an important research field. Batch machine scheduling problem has its root in various application areas and attracted a lot of attention recently. In the paper we consider the problem of scheduling jobs with chain precedence constraints on a batching machine and identical parallel machines to minimize makespan. 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 consider the problem of scheduling the jobs set on a batch processing machine with the objective of minimizing the makespan. There are precedence constraints between the jobs. The problem is denoted by 1|prec,B|Cmax- It hasn't been widely studied in previous related work. A precedence relation Ji -Jj, implies that job Ji must be completed before job Jj can be begun. We discuss the case that are parallel chain-type (i.e.,where every job has at most one direct predecessor and at most one direct successor), which is denoted by 1\chains, B\Cmax.(1)We consider a set of m chains, where n jobs in one chain, a constant number of jobs in the other m - 1 chains, and present a polynomial algorithm for this case.(2)Precedence constrains are as follows: There are only one chain T with n jobs in it and m isolated jobs (i.e. there are no precedence constraints among the m jobs), where m is an arbitray number. There are a number of interestingspecial cases which can be solved in polynomial time.(3)Precedence constrains are as follows: There are m chains with Ui jobs in each chain, where 1 < i < m, and each chain satisfies agreeble. we discuss the optimal algorithm for this case where each batch contains at most two jobs, i.e.B = 2. We show that this problem can be solved in O(n4) time. In fact, we can reduce this problem to a non-bipartie weighted matching problem.In the third chapter, we consider the problem of scheduling jobs with chain precedence constraints on identical parallel machines. The objective function is to minimize the makespan . This problem is denoted by Pm \ chains \ Cmax. It is NP-complete in the strong sense. The best approximation result known so far was a 2 - approximation algorithm that has been derived by Gerhard J.Woeginger . The contribution of this paper is a polynomial time approximation scheme for the problem Pm|chains |Cmax.