caa a22 4500 445838655 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s10951-009-0146-4 doi (NATIONALLICENCE)springer-10.1007/s10951-009-0146-4 Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates [Elektronische Daten] [Imed Kacem, Hans Kellerer] This paper is the first attempt to successfully design efficient approximation algorithms for the single-machine weighted flow-time minimization problem when jobs have different release dates and weights equal to their processing times under the assumption that one job is fixed (i.e., the machine is unavailable during a fixed interval corresponding to the fixed job). Our work is motivated by an interesting algorithmic application to the generation of valid inequalities in a branch-and-cut method. Our analysis shows that the trivial FIFO sequence can lead to an arbitrary large worst-case performance bound. Hence, we modify this sequence so that a new 2-approximation solution can be obtained for every instance and we prove the tightness of this bound. Then, we propose a fully polynomial-time approximation algorithm with efficient running time for the considered problem. Especially, the complexity of our algorithm is strongly polynomial. Springer Science+Business Media, LLC, 2009 Non-availability constraint nationallicence Single-machine nationallicence Flow-time nationallicence Approximation nationallicence Kacem Imed Université Paul Verlaine-Metz, LITA, UFR M.I.M, Ile du Saulcy, 57000, Metz, France aut Kellerer Hans Institut für Statistik und Operations Research, Universität Graz, 8010, Graz, Austria aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/3(2011-06-01), 257-265 1094-6136 14:3<257 2011 14 10951 https://doi.org/10.1007/s10951-009-0146-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-009-0146-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kacem Imed Université Paul Verlaine-Metz, LITA, UFR M.I.M, Ile du Saulcy, 57000, Metz, France aut NATIONALLICENCE 700 1- Kellerer Hans Institut für Statistik und Operations Research, Universität Graz, 8010, Graz, Austria aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/3(2011-06-01), 257-265 1094-6136 14:3<257 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer