• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Maximization of single machine scheduling

Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude (2004), Maximization of single machine scheduling, Annals of operations research, 129, 1-4, p. 21-32. http://dx.doi.org/10.1023/B:ANOR.0000030679.25466.02

Type
Article accepté pour publication ou publié
Date
2004
Journal name
Annals of operations research
Volume
129
Number
1-4
Publisher
Springer
Pages
21-32
Publication identifier
http://dx.doi.org/10.1023/B:ANOR.0000030679.25466.02
Metadata
Show full item record
Author(s)
Aloulou, Mohamed Ali
Kovalyov, Mikhail Y.
Portmann, Marie-Claude
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.
Subjects / Keywords
precedence constraints; release times; maximization problem; semi-active schedules; scheduling

Related items

Showing items related by title and author.

  • Thumbnail
    Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of a computational complexity 
    Portmann, Marie-Claude; Kovalyov, Mikhail Y.; Aloulou, Mohamed Ali (2007) Article accepté pour publication ou publié
  • Thumbnail
    Worst case performance evaluation of flexible solutions in single machine scheduling 
    Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude (2003) Communication / Conférence
  • Thumbnail
    Minimizing the number of late jobs on a single machine under due date uncertainty 
    Aissi, Hassene; Aloulou, Mohamed Ali; Kovalyov, Mikhail Y. (2011) Article accepté pour publication ou publié
  • Thumbnail
    An efficient proactive-reactive scheduling approach to hedge against shop floor disturbance 
    Aloulou, Mohamed Ali; Portmann, Marie-Claude (2005) Chapitre d'ouvrage
  • Thumbnail
    A flexible proactive-reactive approach: the case of an assembly workshop 
    Aloulou, Mohamed Ali; Portmann, Marie-Claude (2008) Chapitre d'ouvrage
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo