Solving Open Job-Shop Scheduling Problems by SAT Encoding
Solving Open Job-Shop Scheduling Problems by SAT Encoding
复制标题
DOI：
10.1587/transinf.e93.d.2316
复制
发表时间：
2010-08
期刊：
影响因子：
--
通讯作者：
Miyuki Koshimura;Hidetomo Nabeshima;H. Fujita;R. Hasegawa
中科院分区：
文献类型：
--
作者：
Miyuki Koshimura;Hidetomo Nabeshima;H. Fujita;R. Hasegawa
本文试图通过将开放式作业车间调度问题转化为布尔可满足性测试问题来求解。编码方法基本上与Crawford和Baker提出的编码方法相同。开放问题是ABZ 8、ABZ 9、YN 1、YN 2、YN 3和YN 4。我们证明了ABZ9的最佳上界678和YN1的最佳上界884确实是最优的。我们还改进了YN 2的上界和ABZ 8、YN 2、YN 3和YN 4的下界。
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.