Maximization Problems in Single Machine Scheduling
Identifieur interne : 006842 ( Main/Exploration ); précédent : 006841; suivant : 006843Maximization Problems in Single Machine Scheduling
Auteurs : Mohamed Ali Aloulou ; Mikhail Y. Kovalyov ; Marie-Claude PortmannSource :
- Annals of Operations Research ; 2004.
English descriptors
- KwdEn :
Abstract
Problems of scheduling n jobs on a single machine to maximize regular objective function are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Only semi-active schedules are of interest, i.e. those for which the jobs cannot be shifted to start earlier without changing the job sequence or violating the feasibility. Such maximization problems arise in predictive-reactive scheduling. Their solutions are used to evaluate the worst-case performance of a set of schedules characterized by a partial order. The most general problem of maximizing maximum cost is solved in O(n3) time. When all release times are equal to zero, it is shown that the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization couterpart with precedence constraints reversed wrt the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n-1 jobs available at the same time. Algorithmic and computational complexity results for several maximization problems follow from these statements.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 003C75
- to stream Crin, to step Curation: 003C75
- to stream Crin, to step Checkpoint: 000670
- to stream Main, to step Merge: 006B45
- to stream Main, to step Curation: 006842
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="486">Maximization Problems in Single Machine Scheduling</title></titleStmt><publicationStmt><idno type="RBID">CRIN:aloulou03c</idno><date when="2004" year="2004">2004</date><idno type="wicri:Area/Crin/Corpus">003C75</idno><idno type="wicri:Area/Crin/Curation">003C75</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">003C75</idno><idno type="wicri:Area/Crin/Checkpoint">000670</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000670</idno><idno type="wicri:Area/Main/Merge">006B45</idno><idno type="wicri:Area/Main/Curation">006842</idno><idno type="wicri:Area/Main/Exploration">006842</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Maximization Problems in Single Machine Scheduling</title><author><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name></author><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name></author><author><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name></author></analytic><series><title level="j">Annals of Operations Research</title><imprint><date when="2004" type="published">2004</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>maximization problems</term><term>precedence constraints</term><term>release times</term><term>schedule flexibility</term><term>scheduling</term><term>single machine</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="4072">Problems of scheduling n jobs on a single machine to maximize regular objective function are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Only semi-active schedules are of interest, i.e. those for which the jobs cannot be shifted to start earlier without changing the job sequence or violating the feasibility. Such maximization problems arise in predictive-reactive scheduling. Their solutions are used to evaluate the worst-case performance of a set of schedules characterized by a partial order. The most general problem of maximizing maximum cost is solved in O(n3) time. When all release times are equal to zero, it is shown that the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization couterpart with precedence constraints reversed wrt the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n-1 jobs available at the same time. Algorithmic and computational complexity results for several maximization problems follow from these statements.</div></front></TEI><affiliations><list></list><tree><noCountry><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</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 006842 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006842 | 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:aloulou03c
|texte= Maximization Problems in Single Machine Scheduling
}}
| This area was generated with Dilib version V0.6.33. |  |