Stochastic and Distributed Anytime Task Scheduling
Identifieur interne : 002325 ( Crin/Checkpoint ); précédent : 002324; suivant : 002326Stochastic and Distributed Anytime Task Scheduling
Auteurs : François Charpillet ; Iadine Chades ; Jean-Michel GalloneSource :
English descriptors
- KwdEn :
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 to build a solution of a one machine scheduling problem within a delay that follows a stochastic distribution. The second application deals with unrelated parallel machines scheduling of non preemptive tasks.
Links toward previous steps (curation, corpus...)
Links to Exploration step
CRIN:charpillet98aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="278">Stochastic and Distributed Anytime Task Scheduling</title></titleStmt><publicationStmt><idno type="RBID">CRIN:charpillet98a</idno><date when="1998" year="1998">1998</date><idno type="wicri:Area/Crin/Corpus">002311</idno><idno type="wicri:Area/Crin/Curation">002311</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">002311</idno><idno type="wicri:Area/Crin/Checkpoint">002325</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">002325</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Stochastic and Distributed Anytime Task Scheduling</title><author><name sortKey="Charpillet, Francois" sort="Charpillet, Francois" uniqKey="Charpillet F" first="François" last="Charpillet">François Charpillet</name></author><author><name sortKey="Chades, Iadine" sort="Chades, Iadine" uniqKey="Chades I" first="Iadine" last="Chades">Iadine Chades</name></author><author><name sortKey="Gallone, Jean Michel" sort="Gallone, Jean Michel" uniqKey="Gallone J" first="Jean-Michel" last="Gallone">Jean-Michel Gallone</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>resource bounded reasoning</term><term>scheduling</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="5394">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 to build a solution of a one machine scheduling problem within a delay that follows a stochastic distribution. The second application deals with unrelated parallel machines scheduling of non preemptive tasks.</div></front></TEI><BibTex type="inproceedings"><ref>charpillet98a</ref><crinnumber>98-R-330</crinnumber><category>3</category><equipe>MAIA</equipe><author><e>Charpillet, François</e><e>Chades, Iadine</e><e>Gallone, Jean-Michel</e></author><title>Stochastic and Distributed Anytime Task Scheduling</title><booktitle>{10th IEEE International Conference on Tools with Artificial Intelligence}</booktitle><year>1998</year><keywords><e>resource bounded reasoning</e><e>scheduling</e></keywords><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 to build a solution of a one machine scheduling problem within a delay that follows a stochastic distribution. The second application deals with unrelated parallel machines scheduling of non preemptive tasks.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002325 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Checkpoint/biblio.hfd -nk 002325 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Checkpoint
|type= RBID
|clé= CRIN:charpillet98a
|texte= Stochastic and Distributed Anytime Task Scheduling
}}
| This area was generated with Dilib version V0.6.33. |  |