Neurosched : a Resource Bounded Scheduler
Identifieur interne : 00B834 ( Main/Exploration ); précédent : 00B833; suivant : 00B835Neurosched : a Resource Bounded Scheduler
Auteurs : Jean-Michel Gallone ; François CharpilletSource :
English descriptors
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 when timing constraints have to be addressed. Obviously these methods are of interest when they provide near optimal solutions and when computational complexity can be controlled. This paper presents such a method based on Hopfield Neural Networks. With this approach, a scheduling problem is solved in an iterative way, finding a solution trough the minimization of an energy function. As the minimization process can fall into a local minimum we can not guarantee that the process will find an optimal solution. Worst, a solution can be missed in some cases. 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. We will demonstrate in this paper that an anytime probabilistic algorithm can be constructed by combining in sequence a set of minimization processes with decreasing convergence speed.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 001D66
- to stream Crin, to step Curation: 001D66
- to stream Crin, to step Checkpoint: 002558
- to stream Main, to step Merge: 00C011
- to stream Main, to step Curation: 00B834
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr" wicri:score="-122">Neurosched : a Resource Bounded Scheduler</title></titleStmt><publicationStmt><idno type="RBID">CRIN:gallone97b</idno><date when="1997" year="1997">1997</date><idno type="wicri:Area/Crin/Corpus">001D66</idno><idno type="wicri:Area/Crin/Curation">001D66</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">001D66</idno><idno type="wicri:Area/Crin/Checkpoint">002558</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">002558</idno><idno type="wicri:Area/Main/Merge">00C011</idno><idno type="wicri:Area/Main/Curation">00B834</idno><idno type="wicri:Area/Main/Exploration">00B834</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="fr">Neurosched : a Resource Bounded Scheduler</title><author><name sortKey="Gallone, Jean Michel" sort="Gallone, Jean Michel" uniqKey="Gallone J" first="Jean-Michel" last="Gallone">Jean-Michel Gallone</name></author><author><name sortKey="Charpillet, Francois" sort="Charpillet, Francois" uniqKey="Charpillet F" first="François" last="Charpillet">François Charpillet</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Neural Networks</term><term>Resource Bounded Reasoning</term><term>Scheduling</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="4945">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 when timing constraints have to be addressed. Obviously these methods are of interest when they provide near optimal solutions and when computational complexity can be controlled. This paper presents such a method based on Hopfield Neural Networks. With this approach, a scheduling problem is solved in an iterative way, finding a solution trough the minimization of an energy function. As the minimization process can fall into a local minimum we can not guarantee that the process will find an optimal solution. Worst, a solution can be missed in some cases. 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. We will demonstrate in this paper that an anytime probabilistic algorithm can be constructed by combining in sequence a set of minimization processes with decreasing convergence speed.</div></front></TEI><affiliations><list></list><tree><noCountry><name sortKey="Charpillet, Francois" sort="Charpillet, Francois" uniqKey="Charpillet F" first="François" last="Charpillet">François Charpillet</name><name sortKey="Gallone, Jean Michel" sort="Gallone, Jean Michel" uniqKey="Gallone J" first="Jean-Michel" last="Gallone">Jean-Michel Gallone</name></noCountry></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B834 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00B834 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= CRIN:gallone97b
|texte= Neurosched : a Resource Bounded Scheduler
}}
| This area was generated with Dilib version V0.6.33. |  |