you're reading...

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


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.




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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

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

Join 68 other followers

%d bloggers like this: