Bin stretching revisited. (English) Zbl 1034.68039
Summary: We study three on-line models of bin stretching on two machines. For the case where the machines are identical and the jobs arrive sorted by non-increasing sizes, we show a tight bound of 10/9 on the competitive ratio. For two related machines, we show a preemptive algorithm with competitive ratio 1 for any speed ratio, and two new non-preemptive algorithms. We prove that the upper bound on the competitive ratio achieved by the non-preemptive algorithms is optimal for almost any speed ratio, and close to optimal for all other speed ratios.
MSC:
68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
68Q25 | Analysis of algorithms and problem complexity |
68W40 | Analysis of algorithms |
90Bxx | Operations research and management science |