Presentation	2004-06-21 Solving Job Shop Scheduling Problems With Multiple SAT Solvers Takehide SOH, Katsumi INOUE,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Many algorithms have recently been proposed for solving propositional satisfiability(SAT). This paper is concerned with a method to solve a job-shop scheduling problem(JSSP) by SAT solvers. Here, JSSP is translated into SAT using Crawford and Baker's method. We consider how due time affect the number of translated clauses. It turns out that due time heavily affects the difficulty of SAT problems. Next, to solve JSSP efficiently, we perform parallel execution of SAT solvers through Multisat, which competitively solves SAT problems by both systematic and stochastic SAT solvers. We also compare Multisat with single SAT solvers for JSSP.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	job-shop scheduling problems / propositional satisfiability / SAT solvers
Paper #	AI2004-4
Date of Issue

Conference Information
Committee	AI
Conference Date	2004/6/14(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Artificial Intelligence and Knowledge-Based Processing (AI)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Solving Job Shop Scheduling Problems With Multiple SAT Solvers
Sub Title (in English)
Keyword(1)	job-shop scheduling problems
Keyword(2)	propositional satisfiability
Keyword(3)	SAT solvers
1st Author's Name	Takehide SOH
1st Author's Affiliation	Graduate School of Science and Technology, Kobe University()
2nd Author's Name	Katsumi INOUE
2nd Author's Affiliation	National Institute of Informatics
Date	2004-06-21
Paper #	AI2004-4
Volume (vol)	vol.104
Number (no)	133
Page	pp.pp.-
#Pages	6
Date of Issue