• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Maximization of single machine scheduling

Thumbnail
Date
2004
Dewey
Recherche opérationnelle
Sujet
precedence constraints; release times; maximization problem; semi-active schedules; scheduling
Journal issue
Annals of operations research
Volume
129
Number
1-4
Publication date
07-2004
Article pages
21-32
Publisher
Springer
DOI
http://dx.doi.org/10.1023/B:ANOR.0000030679.25466.02
URI
https://basepub.dauphine.fr/handle/123456789/1712
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Aloulou, Mohamed Ali
Kovalyov, Mikhail Y.
Portmann, Marie-Claude
Type
Article accepté pour publication ou publié
Abstract (EN)
Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n–1 jobs available at the same time. It is solved in O(mn+n 2) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.