Result: Scheduling as heuristic search with state space reduction
Title:
Scheduling as heuristic search with state space reduction
Authors:
Source:
IBERAMIA 2002 : advances in artificial intelligence (Seville, 12-15 November 2002)Lecture notes in computer science. :815-824
Publisher Information:
Berlin: Springer, 2002.
Publication Year:
2002
Physical Description:
print, 11 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Optimisation. Problèmes de recherche, Optimization. Search problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Intelligence artificielle, Artificial intelligence, Apprentissage et systèmes adaptatifs, Learning and adaptive systems, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Algorithme recherche, Search algorithm, Algoritmo búsqueda, Charge travail, Workload, Carga trabajo, Condition optimalité, Optimality condition, Condición optimalidad, Critère optimalité, Optimality criterion, Criterio optimalidad, Gestion tâche, Task scheduling, Gestión labor, Méthode espace état, State space method, Método espacio estado, Méthode heuristique, Heuristic method, Método heurístico, Ordonnancement, Scheduling, Ordonamiento, Solution optimale, Optimal solution, Solución óptima
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Centro de Inteligencia Artificial. Universidad de Oviedo. Campus de Viesques., 33271 Gijón, Spain
ISSN:
0302-9743
Rights:
Copyright 2003 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Operational research. Management
Operational research. Management
Accession Number:
edscal.14614324
Database:
PASCAL Archive
Further Information
In this paper we confront the Job Shop Scheduling problem by means of an A* algorithm for heuristic state space searching. This algorithm can guarantee optimal solutions, i.e. it is admissible, under certain conditions, but in this case it requires an amount of memory that grows linearly as the search progresses. We hence start by focusing on techniques that enable us to reduce the size of the search space while maintaining the ability of reaching optimal schedules. We then relax some of the conditions that guarantee optimality in order to achieve a further reduction in the number of states visited. We report results from an experimental study showing the extent to which this reduction is worth carrying out in practice.