A BRANCH-AND-BOUND APPROACH FOR A 2-MACHINE FLOWSHOP SCHEDULING PROBLEM

In this paper, we present a branch-and-bound approach for solving a tw o-machine flow shop scheduling problem, in which the objective is to m inimize a weighted combination of job flowtime and schedule makespan. Experimental results show that the algorithm works very well for certa in special cases and moderately well for others. In fact, it is able t o produce optimal schedules for 500-job problems in which the second m achine dominates the first machine. It is also shown that the algorith m developed to provide an upper bound for the branch-and-bound is opti mal when processing times for jobs are the same on both machines. The primary reason for developing the branch-and-bound approach is that it s results can be used to guide other heuristic techniques, such as sim ulated annealing, tabu search and genetic algorithms, in their search for optimal solutions for larger problems.