Design and analysis of algorithms for solving a class of routing shop scheduling problems

Abstract

The routing shop scheduling problems consider the transportation times or sequence dependent setup times in manufacturing environments. A branch-and-bound algorithm for solving the single machine total weighted tardiness problem with unequal release dates is developed. Four global dominance rules as well as a lower bound computational method are proposed to prune the search tree branches. In addition, we present a general purpose heuristic algorithm, named overlapped neighborhood search (ONS) algorithm, to solve a wide variety of sequencing problems. Meta-heuristic algorithms are developed for two multi-machine scheduling problems, the open shop scheduling problem and the routing open shop scheduling problem. New neighborhood structures as wells as an exact operation move feasibility testing method are developed for the open shop scheduling problem and routing open shop scheduling problem. Tabu search algorithms are developed for the open shop and routing open shop scheduling problems.