Critical arc strategies for the reentrant job shop scheduling problem with setups

This thesis presents the Critical Arc Strategies for solving the reentrant job shop scheduling problem with setups. These metaheuristic strategies use combinations of critical path characteristics to gauge which heuristic decisions will have the greatest impact on reducing the average delay of the schedule. This research also investigates feasibility in light of iterative searches for the disjunctive graph of the reentrant job shop scheduling problem with sequence dependent setups.; The class of strategies investigated in this thesis is problem specific and uses the inherent properties of the disjunctive graph to develop critical arc weights for prioritizing the candidate list for arc reversals. There are 3 subclasses of Critical Arc Strategies presented in this thesis. The Delay Weighted Critical Arc (DWCA) strategy uses linear combinations of a critical arc's operation delay and the job delays for which it is a member of the job's specific critical path. The Sequentially Weighted Critical Arc (SWCA) strategies rank the candidates based on the number of critical paths, critical arcs, or accumulated operation delays they influence based on critical path membership. The Exponentially Weighted Critical Arc (EWCA) strategy uses an exponentially weighted average of the critical arc operation delays the candidate influences, which are also based on critical path membership. These strategies aid the metaheuristic in identifying the most significant critical arcs in the graph, allowing it to find improvements faster than traditional tabu search methodologies. An elite candidate list strategy is applied to the candidates, which dynamically restricts the candidate list size based on search performance.; Benchmarking experiments show that the Critical Arc Strategies outperform traditional tabu search candidate list strategies. Additional experiments show the value of applying the metaheuristic strategies to "best" policy generated solutions to minimize average delay in a schedule. These results show the value of applying the Critical Arc Strategies on realistic sized complex problems, such as semiconductor manufacturing facilities.