• 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

Minimizing the number of late jobs on a single machine under due date uncertainty

Thumbnail
Date
2011
Dewey
Recherche opérationnelle
Sujet
Scheduling; Assignment; Robustness; Min-max approach; Scenarios; Uncertainty; Single machine
Journal issue
Journal of Scheduling
Volume
14
Number
4
Publication date
2011
Article pages
351-360
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s10951-010-0183-z
URI
https://basepub.dauphine.fr/handle/123456789/4508
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Aissi, Hassene
Aloulou, Mohamed Ali
Kovalyov, Mikhail Y.
Type
Article accepté pour publication ou publié
Abstract (EN)
We study the problem of minimizing the number of late jobs on a single machine where job processing times are known precisely and due dates are uncertain. The uncertainty is captured through a set of scenarios. In this environment, an appropriate criterion to select a schedule is to find one with the best worst-case performance, which minimizes the maximum number of late jobs over all scenarios. For a variable number of scenarios and two distinct due dates over all scenarios, the problem is proved NP-hard in the strong sense and non-approximable in pseudo-polynomial time with approximation ratio less than 2. It is polynomially solvable if the number s of scenarios and the number v of distinct due dates over all scenarios are given constants. An O(nlog n) time s-approximation algorithm is suggested for the general case, where n is the number of jobs, and a polynomial 3-approximation algorithm is suggested for the case of unit-time jobs and a constant number of scenarios. Furthermore, an O(n s+v−2/(v−1) v−2) time dynamic programming algorithm is presented for the case of unit-time jobs. The problem with unit-time jobs and the number of late jobs not exceeding a given constant value is solvable in polynomial time by an enumeration algorithm. The obtained results are related to a min-max assignment problem, an exact assignment problem and a multi-agent scheduling problem.

  • 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.