Refine
Language
- English (6)
Keywords
- approximation (1)
- online (1)
- scheduling (1)
- stochastic (1)
- total weighted completion time (1)
How to Whack Moles
(2004)
In the classical whack-a-mole game moles that pop up at
certain locations must be whacked by means of a hammer before they
go under ground again. The goal is to maximize the number of moles
caught. This problem can be formulated as an online optimization problem:
Requests (moles) appear over time at points in a metric space and
must be served (whacked) by a server (hammer) before their deadlines
(i.e., before they disappear). An online algorithm learns each request
only at its release time and must base its decisions on incomplete information.
We study the online whack-a-mole problem (wham) on the real
line and on the uniform metric space. While on the line no deterministic
algorithm can achieve a constant competitive ratio, we provide competitive
algorithms for the uniform metric space. Our online investigations
are complemented by complexity results for the offline problem.
In this paper we introduce the notion of smoothed competitive analysis of online
algorithms. Smoothed analysis has been proposed by Spielman and Teng [22] to explain
the behaviour of algorithms that work well in practice while performing very poorly
from a worst case analysis point of view. We apply this notion to analyze the Multi-
Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of
jobs released over time when the processing time of a job is only known at time of
completion.
The initial processing times are integers in the range [1, 2K ]. We use a partial bit
randomization model, where the initial processing times are smoothened by changing
the k least significant bits under a quite general class of probability distributions. We
show that MLF admits a smoothed competitive ratio of O(max((2k /σ)3 , (2k /σ)2 2K−k )),
where σ denotes the standard deviation of the distribution. In particular, we obtain a
competitive ratio of O(2K−k ) if σ = Θ(2k ). We also prove an Ω(2K−k ) lower bound for
any deterministic algorithm that is run on processing times smoothened according to
the partial bit randomization model. For various other smoothening models, including
the additive symmetric smoothening model used by Spielman and Teng [22], we give a
higher lower bound of Ω(2K ).
A direct consequence of our result is also the first average case analysis of MLF. We
show a constant expected ratio of the total flow time of MLF to the optimum under
several distributions including the uniform distribution.
We consider a model for scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling
as a special case. The particular setting we consider is non-preemptive parallel machine scheduling, with the objective to
minimize the total weighted completion times of jobs. We analyze
simple, combinatorial online scheduling policies for that model, and
derive performance guarantees that match performance guarantees previously
known for stochastic and online parallel machine scheduling, respectively.
For processing times that follow NBUE distributions, we
improve upon previously best known performance bounds from
stochastic scheduling, even though we consider a more general
setting.
Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable
first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later.
We introduce the novel concept of an Online Target Date Assignment Problem (OnlineTDAP) as a general framework for online problems with this nature. Requests for the OnlineTDAP become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.g., an appointment with a customer for a
washing machine repair). The cost at a target date is given by the downstream cost, the optimal cost of processing all requests
at that date w.r.t. some fixed downstream offline optimization problem (e.g., the cost of an optimal dispatch for service
technicians). We provide general competitive algorithms for the OnlineTDAP independently of the particular downstream problem,
when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the particular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.
We consider the preemptive and non-preemptive problems of scheduling jobs with precedence constraints on parallel machines with the
objective to minimize the sum of~(weighted) completion times. We investigate an online model in which the scheduler learns about a
job when all its predecessors have completed. For scheduling on a single machine, we show matching lower and upper bounds of~$\Theta(n)$ and~$\Theta(\sqrt{n})$ for jobs with general and equal weights, respectively. We also derive corresponding results on parallel machines.
Our result for arbitrary job weights holds even in the more general stochastic online scheduling model where, in addition to the limited information about the job set, processing times are uncertain. For a
large class of processing time distributions, we derive also an improved performance guarantee if weights are equal.
We consider a non-preemptive, stochastic parallel machine
scheduling model with the goal to minimize the weighted completion
times of jobs. In contrast to the classical stochastic model where jobs
with their processing time distributions are known beforehand, we assume
that jobs appear one by one, and every job must be assigned
to a machine online. We propose a simple online scheduling policy for
that model, and prove a performance guarantee that matches the currently
best known performance guarantee for stochastic parallel machine
scheduling. For the more general model with job release dates we derive
an analogous result, and for NBUE distributed processing times we
even improve upon the previously best known performance guarantee for
stochastic parallel machine scheduling. Moreover, we derive some lower
bounds on approximation.