FMS-scheduling using branch-and-bound with heuristics

In this paper, the generic non-cyclic jobshop scheduling problem is solved by an algorithm based on the classical branch-and-bound method working on a decision tree which represents all possible sequences of operations for the jobshop scheduling problem. The idea of such algorithms is to construct a partial decision tree which contains the optimal solution, but is reduced by cutting of those branches which will only lead to solutions which are worse than the best solution found so far or an upper bound of the cost functional at the optimum which can be estimated from the solutions obtained so far. Unfortunately, for scheduling with respect to minimal tardiness, no efficiently computable bounds are known. To avoid these difficulties we have modified branch-and-bound algorithms by heuristics based on the following idea: Essential parts of the branch-and-bound scheme which guarantee that the method will find the optimal schedule are substituted by heuristics in such a way that the resulti ng algorithm will create at least a good schedule within acceptable computation time. The algorithm was tested for a widely accepted benchmark problem and its results are partial better than those of the best known priority rules.