AI Communications - Volume 28, issue 2

Authors: Wallace, Richard J.

Article Type: Research Article

Abstract: This paper introduces a new kind of local consistency based on the general idea of singleton arc consistency (SAC). This is a reduced form of SAC that only considers neighbourhoods of a variable with a singleton domain; hence, the name “neighbourhood SAC” (NSAC). Like AC and SAC, NSAC has a unique fixpoint, so that NSAC algorithms will produce the same result when applied to a problem regardless of the order in which problem elements are processed. Although NSAC is, of course, dominated by full SAC, on many problems these algorithms produce almost as much filtering with significantly less cost. NSAC …can also be incorporated into full search, as a maintained neighbourhood SAC algorithm. The implementation of NSAC has also inspired two new SAC algorithms. One is a full SAC algorithm that is somewhat more efficient than the classical SAC-1 algorithm on many problems and is much easier to code than more advanced versions of SAC. The other is a partial SAC procedure that performs almost as much domain reduction as full SAC, while requiring much less time than full SAC algorithm on some problems. It is, therefore, a possible alternative to restricted SAC-1. These new algorithms are evaluated in experimental tests, together with SAC-1 and three well-known advanced SAC procedures, on a variety of problem classes. Show more

Keywords: Constraint satisfaction, arc consistency, singleton arc consistency

DOI: 10.3233/AIC-140635

Citation: AI Communications, vol. 28, no. 2, pp. 345-364, 2015

Authors: Mencía, Carlos | Sierra, María R. | Salido, Miguel A. | Escamilla, Joan | Varela, Ramiro

Article Type: Research Article

Abstract: The job shop scheduling problem with an additional resource type has been recently proposed to model the situation where each operation in a job shop has to be assisted by one of a limited set of human operators. We confront this problem with the objective of minimizing the total flow time, which makes the problem more interesting from a practical point of view and harder to solve than the version with makespan minimization. To solve this problem we propose an enhanced dept-first search algorithm. This algorithm exploits a schedule generation schema termed OG&T, two admissible heuristics and some powerful pruning …rules. In order to diversify the search, we also consider a variant of this algorithm with restarts. We have conducted an experimental study across several benchmarks. The results of this study show that the global pruning rules are really effective and that the proposed algorithms are quite competent for solving this problem. Show more

Keywords: Depth first search, pruning by dominance, job shop scheduling problem, operators, restarts

DOI: 10.3233/AIC-140630

Citation: AI Communications, vol. 28, no. 2, pp. 365-381, 2015