## 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**

**Abstract:**

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 ∈ T}l(X)+ y_{min})),

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 *y*_{min} is the earliest end of a

downtime.

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

**Truls Flatberg**

Online bin covering with lookahead and bounded space

**Abstract:**

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**

**Abstract:**

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.