Time: 1:00pm Tuesday 29 October

Location: SIT 459

Speaker: Wiebke Höhn, TU Berlin

Title: Some insights on single machine scheduling with convex cost

Abstract:

We consider a single machine scheduling problem with generalized

min-sum objective. Given some convex cost function, we aim at

computing a schedule minimizing the total weighted completion time

cost. This problem is closely related to scheduling a single machine

with nonuniform processing speed. We give a tight analysis of the

approximation guarantee of the algorithm Highest-Density-First. More

specifically, for the class of convex cost functions we reduce the

task of determining a worst case problem instance to a continuous

optimization problem, which can be solved by standard algebraic or

numerical methods. For monomial cost functions x^k, we show that the

tight approximation factor is asymptotically equal to k^((k-1)/(k+1)).

Moreover, for quadratic cost, we show certain order relations on the

jobs in optimal schedules which allow to drastically reduce the search

space of exact algorithms.

### Like this:

Like Loading...

*Related*

## Discussion

## No comments yet.