caa a22 4500 445838833 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s10951-009-0115-y doi (NATIONALLICENCE)springer-10.1007/s10951-009-0115-y On robust online scheduling algorithms [Elektronische Daten] [Michael Gatto, Peter Widmayer] While standard parallel machine scheduling is concerned with good assignments of jobs to machines, we aim to understand how the quality of an assignment is affected if the jobs' processing times are perturbed and therefore turn out to be longer (or shorter) than declared. We focus on online scheduling with perturbations occurring at any time, such as in railway systems when trains are late. For a variety of conditions on the severity of perturbations, we present bounds on the worst case ratio of two makespans. For the first makespan, we let the online algorithm assign jobs to machines, based on the non-perturbed processing times. We compute the makespan by replacing each job's processing time with its perturbed version while still sticking to the computed assignment. The second is an optimal offline solution for the perturbed processing times. The deviation of this ratio from the competitive ratio of the online algorithm tells us about the "price of perturbations”. We analyze this setting for Graham's algorithm, and among other bounds show a competitive ratio of 2 for perturbations decreasing the processing time of a job arbitrarily, and a competitive ratio of less than 2.5 for perturbations doubling the processing time of a job. We complement these results by providing lower bounds for any online algorithm in this setting. Finally, we propose a risk-aware online algorithm tailored for the possible bounded increase of the processing time of one job, and we show that this algorithm can be worse than Graham's algorithm in some cases. Springer Science+Business Media, LLC, 2009 Robustness nationallicence Online nationallicence Scheduling nationallicence Graham's Algorithm nationallicence Perturbation nationallicence Gatto Michael ETH Zurich, Zurich, Switzerland aut Widmayer Peter ETH Zurich, Zurich, Switzerland aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/2(2011-04-01), 141-156 1094-6136 14:2<141 2011 14 10951 https://doi.org/10.1007/s10951-009-0115-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-009-0115-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Gatto Michael ETH Zurich, Zurich, Switzerland aut NATIONALLICENCE 700 1- Widmayer Peter ETH Zurich, Zurich, Switzerland aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/2(2011-04-01), 141-156 1094-6136 14:2<141 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer