A Branch-and-Bound Algorithm for Flow Shop Scheduling Problems

Publisher Website
Google Scholar
Abstract
This article is concerned with the solution of the flow shop scheduling problem in which all jobs have the same machine ordering. A branch-and-bound algorithm is developed for finding the sequence of J jobs to be processed on M machines which minimizes the schedule time. Thib algorithm consists of branching and bounding processes, but without the backtracking process which guarantees optimality. The procedure employed is that in constructing a subset of feasible sequences, a node representing a partial sequence is branched. Selection of the node depends on the lower-bound concept as a decision rule. This lower bound is based on resolving the conflict of jobs on the last machine. By using this algorithm, the number of explored nodes is considerably reduced and, hence, the computational effort involved in obtaining an optimal or near-optimal solution is decreased. High quality of solutions is obtained. Computationally, this algorithm extends the size of problems that can reasonably be solved.