A Sufficient Optimality Condition and Solvable Special Cases for the Three Machine Flow Shop with Transportations

Abstract

This study considers the problem of scheduling n jobs on three machines with transportation time between machines to minimize the maximum completion time.This problem, when there is no transportation time, is considered NP-hard and, it was discussed by Johnson, while the problem with transportation time is considered more difficult to solve and we are not aware of any research addressing this particular problem.Theoretically, a result about the sufficient optimality condition is derived and proved. Also we derive and prove two results concerning optimality of two special cases for the problem each one get at least (n-1)! optimal sequences.