An efficient SAT algorithm for complex job-shop scheduling

DOI

10.2991/icmse-18.2018.126How to use a DOI?

Keywords

job-shop scheduling; Boolean Satisfiability; coding optimization; exact solution

Abstract

The job-shop scheduling problem (JSSP) is a typical scheduling problem, which belongs to NP-hard problem. This paper tries to solve the complex JSSP by translating it into Boolean Satisfiability Problem. Even though the representation of JSSP in SAT is not a new issue, the solution to the complex JSSP is still a difficult problem because of processing time too long. In this paper, we optimized the SAT encoding method, thus reducing the number of clauses and their processing efficiency in the solver. We used the Ft20 and ABZ8 problem to experiment, the results show that the optimized coding method can greatly improve the processing efficiency.

Copyright

© 2018, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Hong Huang
AU  - Shaohua Zhou
PY  - 2018/05
DA  - 2018/05
TI  - An efficient SAT algorithm for complex job-shop scheduling
BT  - Proceedings of the 2018 8th International Conference on Manufacturing Science and Engineering (ICMSE 2018)
PB  - Atlantis Press
SP  - 683
EP  - 688
SN  - 2352-5401
UR  - https://doi.org/10.2991/icmse-18.2018.126
DO  - 10.2991/icmse-18.2018.126
ID  - Huang2018/05
ER  -