Abstract
In this study, a special situation involving a computationally difficult flowshop scheduling problem is discussed. The objective of this problem is to minimize a weighted combination of job flowtime and schedule makespan. An efficient Branch-and-Bound approach is developed here to solve this problem. The primary reason for developing this Branch-and-Bound approach is that its results can usefully guide other heuristic techniques, such as simulated annealing, tabu search, and genetic algorithms, in finding optimal or good quality solutions to larger sized problems. As evidence of the utility of the proposed approach, we present extensive computational results on random test problems. Our results compare favorably with previously developed algorithms in the literature. Scope and purpose Machine scheduling has been an active area of research for the past four decades. In this paper, we present an efficient Branch-and-Bound approach (with two tighter lower-bounds and one upper-bound) to solve a two-machine flowshop scheduling problem. This problem can be represented as n/m = 2/Flowshop/F, C(max). This procedure was developed from an algorithm first presented by Nagar et al. (Annals of Operations Research, 1995) Based on their work, we present a more effective way to solve these problems.