About | Research | Events | People | Reports | Alumni | Contact | Home
|
June 1-5, 2015
SCHEDULING UNDER UNCERTAINTY
SUMMARY The
workshop's goal is to bring together and promote the dialogue and
collaboration
between researchers in two different communities: ORGANISERS
SPEAKERS Keynote/tutorial speakers:
Additional invited speakers:
MONDAY June 1
TUESDAY June 2
*************************************************************************************************************************************** Matthew Andrews Wireless Scheduling: What Difference Do Walls Make? In this talk we shall pose a number of questions connected to scheduling in high-capacity wireless networks. For example, what is the capacity loss if small cells have to "self-backhaul" their traffic to macro cells? hat is the most effective optimization paradigm for allocating radio resources among small cells? For each question we shall look at how the results will change if the propagation conditions have many discontinuities due to walls. Urtzi Ayesta Non-Intrusive Scheduling of TCP Flows We investigate how
to build a non-intrusive scheduled TCP. For the flows of a
given
origin-destination pair, the objective is to schedule their TCP
segments
(according to some desired criteria) without modifying the network
bandwidth-share used by these flows, which in turn ensures friendliness
with
respect to the rest of the network. We show that in order for a
scheduling
algorithm to be strictly non-intrusive, a sufficient and necessary
condition is
that the sender's and receiver's buffers are infinite. We then show
that, under
the additional condition that segments are neither lost or reordered,
the number
of active TCP flows can be minimized by size-based schedulers, and we
propose a
new scheduler FAIR, which guarantees that the transfer time
of every TCP flow
for the origin-destination pair is reduced. We develop
SCHED_TCP, a user space
implementation of our scheme in order to evaluate its performance on
the
Internet. Our experiments illustrate the non-intrusive property
of SCHED_TCP,
and also illustrate that the performance gain with SCHED_TCP can be
considerable. Our scheme is scalable, and it could be incrementally
deployed on
the Internet improving the user experience on every origin-destination
pair. The
main application domain of our approach correspond to situations in
which there
are many concurrent TCP connections within the same origin-destination
pair,
this might happen as a consequence of HTTP 1.1, Web 2.0 applications
using AJAX
(Google Maps etc.), Split TCP, Parallel Sockets, and also with the use
of
ChromeBook's where the user accesses to all services through the same
back-end
server infrastructure. Yossi Azar Recent results on scheduling with deadlines We
discuss recent results for scheduling with
deadlines of jobs released over time (with processing time and value).
First we
show a logarithmic lower bound for the competitive ratio of any
randomized
preemptive online algorithm for maximizing the value of completed jobs.
This
improves quadratically the Canetti and Irani (STOC 95) previous lower
bound and
matches the simple known upper bounds. The proof is surprisingly
straightforward
and and closes a gap which was supposedly open for 20 years. The lower
bound can
be circumvented by assuming deadline slackness. We consider a committed
model,
in which accepted jobs must be fully completed before their deadline.
We show an
interesting phase transition for a single server at slackness $s=4$.
For any
$s>4$ we develop a constant competitive committed algorithm and
for any $s<4$ we
prove that the competitive ratio of any such algorithm is unbounded.
The
algorithm can be made truthful. Marko Boon A Design Heuristic for Skill Based Parallel Service Systems We study a queueing model of parallel servers of types S = {s1, . . .
, sJ }, serving customers of types C = {c1, . . . , cI} under the policy
FCFS-ALIS. Customers arrive in stationary streams, join the queue and
then abandon or get served. Service is skill based, which is described
by a compatibility graph G, where arc (ci, sj ) indicates that server
type sj can serve customer type ci. Service times depend on both server
and customer type. This generic model is motivated by novel modes of
service seen in areas as diverse as manufacturing, call centers, health
care, data server farms and online retailers. The design in terms of
workforce, skills and service level decisions is an extremely
challenging problem. In this paper we propose a heuristic design
algorithm to determine, for given data and desired service mode, which
can be quality or efficiency driven or both, the required workforce
levels to meet target levels of service quality and work division. The
algorithm is validated through detailed simulation of three
representative examples, indicating that it is remarkably robust and
effective. Gregor Brandt (ORTEC) Why methods for handling uncertainty are often not used Although there is a lot of research being done for stochastic or other methods that should be able to handle uncertainties in scheduling, companies are often not too keen on using these methods or even considering them. In this workshop I will discuss several examples of problems where more advanced methods would have been an improvement but where they are not used. We will go through some cases, which are interesting by themselves, and go into more depth of why companies in these cases were not willing or hesitant to use methods that can handle uncertainties. Christoph Dürr Online Problems with advice Different computational models have been proposed that fit between the online computational model, where no information about futur requests is known, and the offline computational model, where the whole input is known in advance. One of these models is online computation with advice, where some amount of general information is given about future requests. Clearly the competitive ratio is a monotone function of the amount of given advice. For some problems improving the competitive below some threshold the necessary advice increases from a constant to a logarithm. We illustrate this model with recent results on the bin packing problem, which is joint work with Spyros Angelopoulos, Shahin Kamali, Marc Renault and Adi Rosén. Leah Epstein Rent or Buy problems with a Fixed Time Horizon and Other Online Scheduling Problems with Rejection We study several variants of
a fixed
length ski rental problem and related scheduling problems with
rejection. A ski season consists of m days, and an equipment of cost 1
is to be used during these days. The equipment can be bought on any
day, in which case it can be used without any additional cost starting
that day and until the vacation ends. On each day, the algorithm is
informed with the current non-negative cost of renting the equipment.
As long as the algorithm did not buy the equipment, it must rent it
every day of the vacation, paying the rental cost of each day of
rental. We consider the case of arbitrary, non-increasing, and
non-decreasing rental costs. We consider the case where the season
cannot end before the m-th day, and the case that it can end without
prior notice. We propose optimal online algorithms for all values of m
for all variants. The optimal competitive ratios are either defined by
solutions of equations (closed formulas or finite recurrences) or sets
of mathematical programs, and tend to 2 as m grows. We will also
discuss related scheduling problems with rejection. Asaf Levin Adaptivity in variants of the stochastic knapsack problem. We study stochastic variants
of the knapsack problem in
which item values are deterministic and item sizes are independent
random
variables with known, arbitrary distributions. Items are placed in the
knapsack
sequentially, and the act of placing an item in the knapsack
instantiates its
size. The goal is to compute a policy for insertion of the items, that
maximizes
the expected total value of items placed in the knapsack. The variants
of the
problem differ in the formula for computing the total value of the
solution
obtained by the policy. (Presentation not available) Nicole Megow Online Resource Minimization We consider the fundamental
resource minimization
problem in which we ask for the minimum number of machines that is
necessary for
feasibly scheduling preemptive jobs with release dates and hard
deadlines. We
study the online variant of this problem in which the job set is
unknown in
advance. Every job becomes known to an algorithm only at its release
date. We
discuss two complementary special cases of the problem, namely, laminar
instances and agreeable instances, for which we provide an O(log
m)-competitive
and an O(1)-competitive algorithm, respectively. As a main result we
present a
general O(m^2 log m)-competitive algorithm, where m is the optimal
number of
machines used in an offline solution. This is particularly interesting
as it is
the first result that does not directly depend on the job sizes or
number of
jobs. Rolf Möhring Stochastic Scheduling: History and Challenges Stochastic scheduling problems have been investigated since the 50ies. Most results address the case that processing times are random but precedence and resource constraints are deterministic. Scheduling is then done by policies which consist of a process of decisions over time that are based on the observed past and the a priori knowledge of the distribution of processing times. The objective is to find a policy that minimizes a regular performance measure such as makespan or weighted sum of completion times in expectation. Policies may be classified according to their way of resolving the resource conflicts. Suitable combinatorial properties of such policies have led to optimality and stability results, to computational methods for constructing policies, and also to approximation algorithms. I will give a survey on important results for such problems and highlight some challenging open questions. At the end, I will also address the problem of how to calculate risk measures when a scheduling project is carried out by a particular policy. Such risk measures have been applied successfully to shutdown and turnaround scheduling in chemical manufacturing. Kamesh Munagala Prophet Inequalities and Stochastic Optimization Many recent advances in designing approximately optimal policies for stochastic optimization problems use variants of prophet inequalities. In this tutorial, we will begin by defining these inequalities, and presenting several different proofs using linear programming and duality. We will then consider widely studied stochastic optimization problems such as multi-unit auctions, stochastic knapsack, and multi-armed bandits, and show how prophet-inequality like ideas provide both linear programming relaxations, as well as techniques to convert these relaxations to approximately optimal policies. We will show the connection between these policies and the classic index policies. Time permitting, we will describe the limitations of these inequalities, and some cases where stronger linear programs are needed. Mike Pinedo Scheduling Customer Arrivals with Overbooking in Service Systems with No-Shows We analyze a discrete
multi-server queueing model for
scheduling customer arrivals under no-shows. Customers have different
waiting
cost coefficients and different no-show rates, reflecting their type
and their
history in attending scheduled appointments respectively. The challenge
is to
assign customers to time slots so that the service system utilizes its
resources
efficiently, and customers enjoy short waiting times. Theoretical and
heuristic
guidelines are provided for the effective practice of appointment
overbooking to
offset no-shows. For the case of heterogeneous customers, we provide
structural
properties of an optimal schedule and we introduce a new sequencing
rule. When
customers come from a homogeneous pool, recursive expressions for the
performance measures of interest are derived and we provide an upper
bound for
the optimal overbooking level. Our extensive numerical experiments
reveal
further properties and patterns Kirk Pruhs (Tutorial) An Introduction to Competitive Analysis in Online Scheduling There is a large body of literature studying algorithms for scheduling/prioritizing jobs that arrive at the server over time. A competitive algorithm is one that guarantees that the provided quality of service is not too much worse than the best possible quality of service that could have been provided. I will introduce the most important basic definitions, concepts, and some basic algorithm analysis techniques. Competitive Analysis in Online Scheduling using Potential Functions and Dual Fitting There is a large body of literature studying algorithms for scheduling/prioritizing jobs that arrive at the server over time. A competitive algorithm is one that guarantees that the provided quality of service is not too much worse than the best possible quality of service that could have been provided. I will cover the two state of the art algorithm analysis techniques in this area: potential functions and dual fitting analysis. Ramandeep Randhawa Scheduling Homogeneous Impatient Customers Customer impatience has become an integral component of analyzing services, especially in the context of call centers. Typically, when customers arrive to such systems, they seem identical or homogeneous, however, from the system's perspective, as they wait in the queue, their residual willingness to wait changes. For instance, a customer who has already waited for 10 minutes may have a different residual willingness to wait as compared with a customer who has only waited for 1 minute. In this manner, as time progresses, customers become differentiated on their estimated patience levels. We exploit this dimension of customer heterogeneity to construct scheduling policies in overloaded systems that dynamically prioritize customers based on their time in queue in order to optimize any given system performance metric. Interestingly, the optimal policy has a very simple structure, and we find that implementing it can lead to significant improvements over the first come first serve policy. R. Srikant Performance Analysis of Scheduling Algorithms for Switches and Data Centers We will consider scheduling
algorithms that are widely used
in high-speed switches in the Internet and data centers. In the first
part of
the talk, we will review the connection between these algorithms and
maximum
weighted matchings. In particular, we will show how these algorithms
naturally
arise from throughput maximization considerations in both deterministic
and
stochastic settings. We will then move beyond throughput maximization
and
formulate questions of interest in studying the delay or queue length
performance of these algorithms. In the second part of the talk, we
will present
a new technique for analyzing the delay performance using drift
techniques. The
basic idea is to exploit the following simple fact: the expected drift
of any
reasonable function of the queue length must be equal to zero in
steady-state.
Using this simple fact. we will establish bounds on the total queue
length in
the network, and show that these bounds are tight in some regimes. Sebastian Stiller How to order a waiting list? How to order the waiting list for an overbooked flight? This amounts to the problem of packing a knapsack without knowing its capacity. Whenever we attempt to pack an item that does not fit, the item is discarded; if the item fits, we have to include it in the packing. We show that there is always a policy that packs a value within factor 2 of the optimum packing, irrespective of the actual capacity. If all items have unit density, we achieve a factor equal to the golden ratio R = 1.618. Both factors are shown to be best possible. In fact, we obtain the above factors using packing policies that are universal in the sense that they fix a particular order of the items and try to pack the items in this order, independent of the observations made while packing. We give efficient algorithms computing these policies. On the other hand, we show that, for any R > 1, the problem of deciding whether a given universal policy achieves a factor of R is coNP-complete. If R is part of the input, the same problem is shown to be coNP-complete for items with unit densities. Finally, we show that it is coNP-hard to decide, for given R, whether a set of items admits a universal policy with factor R, even if all items have unit densities. This is joint work with Yann Disser, Max Klimm, and Nicole Megow. Alexander Stolyar Pull-based load distribution in large-scale heterogeneous service systems
We consider a heterogeneous service system, consisting of several (different) large server pools, and study an asymptotic regime in which the customer arrival rate and pool sizes scale to infinity simultaneously. We introduce a 'pull-based' scheme (called PULL), for routing arriving customers to servers and prove that, under subcritical load, both waiting times and blocking probabilities asymptotically vanish. In particular, the performance of PULL is vastly superior to that of the celebrtated 'power-of-d-choices' (JSQ(d)) routing algorithm.
Jean Walrand
Maximum Throughput Scheduling This talk reviews recent
results on maximum throughput
scheduling. In particular, we review the stability of longest
queue first
policies and the design of robust policies that do not assume knowledge
of
service times. We also discuss the stability of maximum
weighted deficit for
processing networks.
Andreas Wiese
On Approximating Storage Allocation Problems as Good as Their Siblings
Packing
problems are a fundamental
class of problems studied in combinatorial optimization. Three
particularly
important and well-studied questions in this domain are the
Unsplittable Flow on
a Path problem
(Presentation not available)
Kuang Xu Capacity of Information Processing Systems We study an information processing system where a stream
of
jobs, each associated with a hidden label, is to be inspected by a
group of experts. Each inspection produces a noisy result which depends
on the job's hidden label and the type of the corresponding expert.
Meanwhile, an inspection also occupies the expert for one unit of time,
during which she cannot process other jobs. The decision maker's
objective is to dynamically assign inspections so as to accurately
uncover the jobs' hidden labels, while using only a minimum number of
experts to ensure system stability. We are motivated by applications
from areas such as crowdsourcing, machine learning, and experimental
design, where information for a large number of items is to be
gathered, using a limited set of experts or computational resources.
Our main result is an asymptotically optimal inspection policy, under
which the required number of experts matches a lower bound, as the
probability of labeling error tends to zero. (Presentation not available) Zhong Yuan Efficient coflow scheduling in data center networks Communication in data center jobs (such as the shuffle
operations in
MapReduce applications) often involve many parallel data flows, which
may be
processed simultaneously. This highly parallel structure presents new
scheduling
challenges in optimizing job-level performance objectives in data
centers.
PRACTICAL INFORMATION ● VenueEurandom, Mathematics and Computer Science Dept, TU Eindhoven, Den Dolech 2, 5612 AZ EINDHOVEN, The Netherlands
Eurandom is
located on the campus of Eindhoven
University of
Technology,
in the
Metaforum building
(4th floor) (about
the building). The university is
located at 10 minutes walking distance from Eindhoven main railway
station (take
the exit north side and walk towards the tall building on the right
with the
sign TU/e).
● RegistrationRegistration is free, but compulsory for speakers and participants. Please follow the link: REGISTRATION
● AccommodationFor invited participants, we will take care of accommodation. Other attendees will have to make their own arrangements. We have a preferred hotel, which can be booked at special rates. Please email Patty Koorn for instructions on how to make use of this special offer. For other hotels around the university, please see: Hotels (please note: prices listed are "best available"). More hotel options can be found on the webpages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven.
● TravelFor those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages or see Eurandom web page location. Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl The University can be reached easily by car from the highways leading to Eindhoven (for details, see our route descriptions or consult our map with highway connections.
● Conference facilities : Conference room, Metaforum Building MF11&12The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.
● Conference SecretariatUpon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.
● CancellationShould you need to cancel your participation, please contact Patty Koorn, the Workshop Officer. There is no registration fee, but should you need to cancel your participation after January 2, 2014, we will be obliged to charge a no-show fee of 30 euro.
● Friday eveningOn Friday evening (June 5) there is a friendly football (soccer) match between the Netherlands and USA, held in the Amsterdam ArenA. Some of the participants are going to the match, and making it a very sociable end to the workshop week! Should you want to join this sportive activity, tickets are on sale from: VIAGOGO .
● ContactMrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl SPONSORSThe organisers acknowledge the financial support/sponsorship of:
Last updated
02-07-15,
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
.jpg)
