A local search algorithm for a SAT representation of scheduling problems

被引：0

作者：

Antonio Cruz-Chavez, Marco ^{[1
]}

Rivera-Lopez, Rafael ^{[2
]}

机构：

[1] Autonomous Univ Morelos State, CIICAp, Av Univ 1001, Cuernavaca 62209, Morelos, Mexico

[2] Technol Inst Veracruz, Mexico City 91860, DF, Mexico

来源：

COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2007, PT 3, PROCEEDINGS | 2007年 / 4707卷

关键词：

job shop; satisfiability; SAT formula; disjunctive graph; reduced SAT codification of [!text type='JS']JS[!/text]SP;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper presents the application of a local search algorithm for a logical representation of the Job Shop Scheduling Problem (JSSP). This logical representation represents the JSSP transformed as a satisfiability problem (SAT). The proposed algorithm uses a local search in a wide neighborhood. This algorithm, called Walk Wide Search - SAT, is a variant of the WalkSAT algorithm. This search is possible because the included tabu list prevents an excessive number of repetitions of movements during the search process. This paper describes the algorithm and compares results of Walk Wide Search - SAT to WalkSAT.

引用

页码：697 / +

页数：3

共 20 条

[1] [Anonymous], 2000, P 2 ANN C GEN EV COM
[2] MACHINE SEQUENCING VIA DISJUNCTIVE GRAPHS - AN IMPLICIT ENUMERATION ALGORITHM
BALAS, E
[J]. OPERATIONS RESEARCH, 1969, 17 (06) : 941 - &
[3] Brucker P, 2007, Scheduling Algorithms, V3, DOI DOI 10.1007/978-3-540-69516-5
[4] Conway R.W., 1967, Theory of Scheduling
[5] CRAWFORD JM, 1994, PROCEEDINGS OF THE TWELFTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS 1 AND 2, P1092
[6] Cruz-Chavez MA, 2004, LECT NOTES ARTIF INT, V3070, P860
[7] CRUZCHAVEZ MA, 2006, IN PRESS LNCS
[8] DEFU Z, 2005, P 9 INT C COMP SUPP, V2, P1112
[9] El-Mihoub T.A., 2006, ENG LETT, V13, P2
[10] Frausto-Solis J, 2004, LECT NOTES COMPUT SC, V3046, P553

← 1 2 →