Method for job shop scheduling based on dynamic consistency enforcing technique

For improving the average efficiency and reducing the average complexity of the basic backtrack search procedure, Dynamic Consistency Enforcing Technique (DCET) is put forward to prune the search space by eliminating local inconsistencies that cannot participate in a global scheduling solution. The DCET includes two algorithms, i.e. precedence and capacity consistency enforcing algorithm. Precedence consistency enforcing algorithm can effectively prune reservations of unscheduled operations upstream or downstream within the same job by earlier reservation assignments. For more difficult capacity constraints, capacity consistency enforcing algorithm is carried out to prune possible reservations of the remaining unscheduled operations which compete for the same resource with scheduled operation in current search space. The simulation indicates that DCET can greatly reduce both the frequency and the amount of backtrack, thus greatly improving the search efficiency of job shop scheduling.