Method for job shop scheduling based on dynamic consistency enforcing technique

Hongan Yang, Shudong Sun, Shubin Si, Chen Liang

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)523-527
Number of pages5
JournalXibei Gongye Daxue Xuebao/Journal of Northwestern Polytechnical University
Volume25
Issue number4
StatePublished - Aug 2007

Keywords

  • Capacity consistency
  • Dynamic consistency enforcing techniques
  • Job shop scheduling
  • Precedence consistency
  • Search efficiency

Fingerprint

Dive into the research topics of 'Method for job shop scheduling based on dynamic consistency enforcing technique'. Together they form a unique fingerprint.

Cite this