• DocumentCode
    1673045
  • Title

    Minimizing the number of late jobs in single machine scheduling with nested execution intervals

  • Author

    Briand, Cyril ; Ourari, Samia ; Bouzouia, Brahim

  • Author_Institution
    LAAS-CNRS, Univ. de Toulouse
  • Volume
    2
  • fYear
    2006
  • Firstpage
    1172
  • Lastpage
    1177
  • Abstract
    This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Job execution intervals are assumed to be nested each inside the other, like Russian dolls. The objective is to minimize the number of late jobs. For this problem, denoted as 1|ri , nested| SigmaUi, a new dominance condition and an optimal O(n3) solving procedure are proposed
  • Keywords
    single machine scheduling; Russian dolls; dominance condition; fixed processing time; nested job execution intervals; single machine scheduling; Algorithm design and analysis; Dynamic programming; Heuristic algorithms; Polynomials; Single machine scheduling; Sufficient conditions; Uninterruptible power systems; dominance conditions; nested execution intervals; single machine scheduling;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Service Systems and Service Management, 2006 International Conference on
  • Conference_Location
    Troyes
  • Print_ISBN
    1-4244-0450-9
  • Electronic_ISBN
    1-4244-0451-7
  • Type

    conf

  • DOI
    10.1109/ICSSSM.2006.320674
  • Filename
    4114656
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1673045