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

Aissi, Hassene; Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.

dc.contributor.author	Aissi, Hassene
dc.contributor.author	Aloulou, Mohamed Ali
dc.contributor.author	Kovalyov, Mikhail Y.
dc.date.accessioned	2010-06-30T13:38:05Z
dc.date.available	2010-06-30T13:38:05Z
dc.date.issued	2011
dc.identifier.uri	https://basepub.dauphine.fr/handle/123456789/4508
dc.language.iso	en	en
dc.subject	Scheduling	en
dc.subject	Assignment	en
dc.subject	Robustness	en
dc.subject	Min-max approach	en
dc.subject	Scenarios	en
dc.subject	Uncertainty	en
dc.subject	Single machine	en
dc.subject.ddc	003	en
dc.title	Minimizing the number of late jobs on a single machine under due date uncertainty	en
dc.type	Article accepté pour publication ou publié
dc.description.abstracten	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.	en
dc.relation.isversionofjnlname	Journal of Scheduling
dc.relation.isversionofjnlvol	14
dc.relation.isversionofjnlissue	4
dc.relation.isversionofjnldate	2011
dc.relation.isversionofjnlpages	351-360
dc.relation.isversionofdoi	http://dx.doi.org/10.1007/s10951-010-0183-z	en
dc.description.sponsorshipprivate	oui	en
dc.relation.isversionofjnlpublisher	Springer	en
dc.subject.ddclabel	Recherche opérationnelle	en

Files in this item

Files	Size	Format	View
There are no files associated with this item.

This item appears in the following Collection(s)

LAMSADE : Publications

Show simple item record

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

Files in this item

This item appears in the following Collection(s)

Related items