>
you're reading...
Announcements

SACT Seminar: Some insights on single machine scheduling with convex cost

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.

 

Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 64 other followers

%d bloggers like this: