Abstract

This paper considers the problem of scheduling 'n' jobs on three machine flow shop with transportation times between the machines to minimize the maximum completion time. This problem is known as NP-hard. Theoretically, results concerning optimality for two special cases of the problem are given. Special attention is also given to branch and bound (BAB) and local search methods. The BAB algorithms use the quickly computed but possibly rather weak lower bounds obtained from relaxation of machines capacity constraints. The (BAB) algorithms are then tested on a large set of test problems. Also, we develop, compare and test different local search methods (Descent, Simulation Annealing, Threshold Accepting, Tabu Search, Genetic Algorithm, Ant Colony Algorithm) for the problem. Computational experience is found that these local search algorithms solve the problem to 7000 jobs with reasonable time.

The article was added to IASJ on 2013-11-07

291 Total full text downloads since the date of addition