A branch and bound algorithm in optimizing job shop scheduling problems

Abstract

One primary objective in solving the job shop scheduling problems is to minimize the makespan, which is a particularly hard combinatorial optimization problem. The problem has been known for years and a vast majority of researches had been focused to solve the problem using a variety of optimization methods such as the branch and bound (B&B). However, the B&B method is considered as only suitable for small and medium size problems due its prohibitive computational time. In this paper, we implement the B&B method using the disjunctive programming approach to obtain optimal solutions for job shop scheduling problem. The B&B program developed is tested on a set of benchmark data and the results obtain are compared to best known from the previous work. Based on the comparison, we conclude that the branch and bound algorithm is considerable as a solution tool for small, medium, as well as large job shop problems.