IEICE TRANSACTIONS on Information
Solving Open Job-Shop Scheduling Problems by SAT Encoding
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E93-D No.8 pp.2316-2318
- Publication Date
- 2010/08/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E93.D.2316
- Type of Manuscript
- LETTER
- Category
- Artificial Intelligence, Data Mining
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Miyuki KOSHIMURA, Hidetomo NABESHIMA, Hiroshi FUJITA, Ryuzo HASEGAWA, "Solving Open Job-Shop Scheduling Problems by SAT Encoding" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 8, pp. 2316-2318, August 2010, doi: 10.1587/transinf.E93.D.2316.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.2316/_p
Copy
@ARTICLE{e93-d_8_2316,
author={Miyuki KOSHIMURA, Hidetomo NABESHIMA, Hiroshi FUJITA, Ryuzo HASEGAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Solving Open Job-Shop Scheduling Problems by SAT Encoding},
year={2010},
volume={E93-D},
number={8},
pages={2316-2318},
abstract={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.},
keywords={},
doi={10.1587/transinf.E93.D.2316},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - Solving Open Job-Shop Scheduling Problems by SAT Encoding
T2 - IEICE TRANSACTIONS on Information
SP - 2316
EP - 2318
AU - Miyuki KOSHIMURA
AU - Hidetomo NABESHIMA
AU - Hiroshi FUJITA
AU - Ryuzo HASEGAWA
PY - 2010
DO - 10.1587/transinf.E93.D.2316
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2010
AB - 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.
ER -
English
