Solving Open Job-Shop Scheduling Problems by SAT Encoding

Miyuki KOSHIMURA  Hidetomo NABESHIMA  Hiroshi FUJITA  Ryuzo HASEGAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.8   pp.2316-2318
Publication Date: 2010/08/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.2316
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Artificial Intelligence, Data Mining
Keyword: 
combinatorial problem,  scheduling,  SAT encoding,  job-shop scheduling,  makespan,  

Full Text: PDF(68.1KB)>>
Buy this Article



Summary: 
This paper tries to solve open Job-Shop Scheduling Problems (JSSP) by translating them into Boolean Satisfiability Testing Problems (SAT). The encoding method is essentially the same as the one proposed by Crawford and Baker. The open problems are ABZ8, ABZ9, YN1, YN2, YN3, and YN4. We proved that the best known upper bounds 678 of ABZ9 and 884 of YN1 are indeed optimal. We also improved the upper bound of YN2 and lower bounds of ABZ8, YN2, YN3 and YN4.