Stochastic & Distributed Anytime Task Scheduling

François Charpillet 1 Iadine Chadès 1 Jean-Michel Gallone 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Scheduling techniques have been intensively studied by several research communities and have been applied to a wide range of applications in computer and manufacturing environments. Most of the scheduling problems are NP-Hard. Therefore, heuristics and approximation algorithms must be used for large problems. Obviously these methods are of interest when they provide near optimal solutions and when computational complexity can be controlled. For this purpose, we have developed a method based on Hopfield Neural Network model. This approach permits to solve in an iterative way a scheduling problem, finding a solution through the minimization of an energy function. An interesting property of this approach is its capacity to trade-off the quality for computation time. Indeed, the convergence speed of the minimization process can be tuned by adapting several parameters that influence the quality of the results. By tuning these parameters, we can built a library of a set of run-time executions (contracts) of the Hopfield minimization process with different characteristics (quality, efficiency). We present in this paper two applications exploiting the advantage of having available anytime contract algorithms. The first application illustrates how the availability of a library of contract algorithms make it possible to build a solution to one machine scheduling problems within a delay that follows a stochastic distribution. The second application deals with unrelated parallel machines scheduling of non preemptive tasks.
Type de document :
Communication dans un congrès
Workshop of the 13th Biennial European Conference on Artificial Intelligence ECAI98, on Monitoring and control of real-time intelligent systems, 1998, Brighton, United Kingdom. 7 p, 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00098551
Contributeur : Publications Loria <>
Soumis le : lundi 25 septembre 2006 - 17:03:18
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51

Identifiants

  • HAL Id : inria-00098551, version 1

Collections

Citation

François Charpillet, Iadine Chadès, Jean-Michel Gallone. Stochastic & Distributed Anytime Task Scheduling. Workshop of the 13th Biennial European Conference on Artificial Intelligence ECAI98, on Monitoring and control of real-time intelligent systems, 1998, Brighton, United Kingdom. 7 p, 1998. 〈inria-00098551〉

Partager

Métriques

Consultations de la notice

283