Permutation Scheduling Problems For Two-machines

Scheduling problems are important combinatorial optimization problems. In the classical theory, we often assume that a job can be processed on only one machine at a time. However, in some situations, a job can be processed on more than one machine at the same time. In this paper, we assume that each job has two working procedure,which need to be processed separately on machine MA and machine MB. We limit that each job should be processed at the same sequence on the two machines. But different from the two-machines permutation flow shop scheduling problems, the two working procedure of each job, here, can be processed on the two machines at the same time. In this paper, we consider total completion time problem and tardy job number problem.Chapter 1 introduce the definition and preliminary knowledge as well as the background of scheduling problems.In chapter 2, we discuss total completion time permutation scheduling problem for two machines. Under the limiting total completion time of machine MA(no greater than a given constant M), we discuss the problem of minimizing the total completion time of machine MB. We describe a polynomial time algorithm of this problem, and prove that every sequence we get from the algorithm 2.2 is a noninferior solution.In chapter 3, we discuss tardy job number permutation sequencing scheduling problem for two machines. We describe a polynomial time algorithm of minimizing the total number of tardy jobs ∑Uj.Chapter 4 gives summary of the thesis, and further research work is suggested.