A Study Of The Algorithm And Computational Complexity For A Type Of TMF Scheduling Problem

Scheduling is a kind of important combinatorial optimization problem. In the classical scheduling it is assumed that each task is to be processed by at most one processor at a time. However, there are many situations tasks have to be processed on more than one processor at a time. Therefore, the modern scheduling problems come out, in which tasks are processed on more than one processor at a time. It is a new type of scheduling problems, and used widely in various areas, so the considering of the problem are necessary.In this paper, we consider a type of modern scheduling problem in which some tasks are processed on more than one processor at a time. We call this kind of problem Two-stage Multi-processor Flow shop (TMF). At first, it introduces some basic theory of scheduling problem, also reviews the researching actuality. In chapter 3, the problem is proved to be NP-complete, no good polynomial algorithm can be found; In chapter 4, a branch and bound algorithm for the problem is given; In chapter 5, we discuss a few polynomial solvable cases of the problem and present the solution algorithms; In chapter 6, we present three heuristic algorithms, provide the upper bounds of the performance ratio in worse case for the algorithms and show that the algorithms are effective. At last, the VC++ programming code is given to solve the problem.