caa a22 4500 445838663 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s10951-010-0183-z doi (NATIONALLICENCE)springer-10.1007/s10951-010-0183-z Minimizing the number of late jobs on a single machine under due date uncertainty [Elektronische Daten] [Hassene Aissi, Mohamed Aloulou, Mikhail Kovalyov] 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. Springer Science+Business Media, LLC, 2010 Scheduling nationallicence Single machine nationallicence Uncertainty nationallicence Scenarios nationallicence Min-max approach nationallicence Robustness nationallicence Assignment nationallicence Aissi Hassene LAMSADE, Paris Dauphine University and CNRS, Place du Maréchal de Lattre de Tassigny, 75775, Paris Cedex 16, France aut Aloulou Mohamed LAMSADE, Paris Dauphine University and CNRS, Place du Maréchal de Lattre de Tassigny, 75775, Paris Cedex 16, France aut Kovalyov Mikhail United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012, Minsk, Belarus aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 351-360 1094-6136 14:4<351 2011 14 10951 https://doi.org/10.1007/s10951-010-0183-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0183-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Aissi Hassene LAMSADE, Paris Dauphine University and CNRS, Place du Maréchal de Lattre de Tassigny, 75775, Paris Cedex 16, France aut NATIONALLICENCE 700 1- Aloulou Mohamed LAMSADE, Paris Dauphine University and CNRS, Place du Maréchal de Lattre de Tassigny, 75775, Paris Cedex 16, France aut NATIONALLICENCE 700 1- Kovalyov Mikhail United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012, Minsk, Belarus aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 351-360 1094-6136 14:4<351 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer