Exerct and Near Optimal Solution for Three Machine Flow Shop Scheduling


In this paper we consider F3/ /C.o* problem in which theprocessing order is assumed to be the same on each machine, theresulting problem is called the permutation flow shop problem. Theobjective is to find a processing order on each machine such thatthe makespan C*o* , which is the completion time of the last job isminimized. This problem is NP-hard, hence the existence of apolynomial time algorithm for finding an optimal solution isunlikely. This complexity result leads us to use an enumerationsolution approach. In this paper rve proposc a branch and boundal-eorithm to solve this problem. Also we develop fastapproximation algorithms yielding near optimal solution. We