Contributed Session Fri.2.H 3010

Friday, 13:15 - 14:45 h, Room: H 3010

Cluster 1: Approximation & online algorithms [...]

Scheduling and online algorithms


Chair: Chris Potts



Friday, 13:15 - 13:40 h, Room: H 3010, Talk 1

Liliana Grigoriu
Scheduling on uniform processors with at most one downtime on each machine

Coauthor: Donald K. Friesen


When scheduling on parallel machines, these may exhibit periods of unavailability due to maintenance or failures, or to due jobs that must execute at predefined times. We consider the problem of non-preemptively scheduling a given set of independent tasks on uniform processors with predefined periods of unavailability, with the aim of minimizing the maximum completion time. This problem is strongly NP-hard. For the case when there is at most one downtime on each machine, we give a simple polynomial Multifit-based approximation algorithm, the schedules of which finish within 1.5 the maximum between the end of the optimal schedule and the latest end of a downtime. Even for same-speed processors, no polynomial algorithm can insure a better worst-case bound unless P=NP. The time complexity of
the algorithm is O(nlogn+(mlogm+nm)log(∑X ∈ Tl(X)+ ymin)),
where n is the number of tasks, m is the number of processors, T
is the set of tasks, l(X) is the time needed to process task X on
the slowest processor, and ymin is the earliest end of a



Friday, 13:45 - 14:10 h, Room: H 3010, Talk 2

Truls Flatberg
Online bin covering with lookahead and bounded space


We consider a problem motivated from a practical packing problem in the fish industry. As fish arrive on the packing line their weight and quality are registered, thus giving a lookahead on the items to be packed by robots into identical crates with a required minimum total weight.
This problem can be modeled as an online bin covering problem with lookahead and bounded space. The focus of this study was to examine the effect of the lookahead on the quality of the packing. That is, if we know the weight of the N next items, how does the solution quality vary with N as we go from an online problem towards the offline problem.
We examined the question by implementing a few simple algorithms and testing them on data based on the real world planning problem.



Friday, 14:15 - 14:40 h, Room: H 3010, Talk 3

Chris Potts
On-line production planning to maximize on-time orders

Coauthors: Nicholas G. Hall, Marc E. Posner


We consider a production planning environment with two
planning periods. Detailed planning occurs in the first
period, where complete information is known about a set
of orders that are available at the start of this
period. An additional set of orders becomes available
at the start of the second planning period. The objective is to maximize the value associated with the proportion of orders that complete processing by their due dates. We derive an upper bound on the competitive ratio of any algorithm,
relative to the performance of an algorithm with
perfect information about the second set of orders.
This ratio depends on the relative lengths of the two
planning periods. We describe a simple, efficient
algorithm that delivers a solution which asymptotically
achieves this upper bound ratio as the number of jobs
becomes large.


  California Payday Loans. Moreover, to order Cialis Daily online is highly advantageous because it interacts well with the small portions of alcohol and food.