A Comparative Study of Two-phase Heuristic Approaches to General Job Shop Scheduling Problem

Abstract. Scheduling is one of the most important issues in the planning and operation of production systems. This paper investigates a general job shop scheduling problem with reentrant work flows and sequence dependent setup times. The disjunctive graph representation is used to capture the interactions between machines in job shop. Based on this representation, four two-phase heuristic procedures are proposed to obtain near optimal solutions for this problem. The obtained solutions in the first phase are substantially improved by reversing the direction of some critical disjunctive arcs of the graph in the second phase. A comparative study is conducted to examine the performance of these proposed algorithms