Approximating Scheduling Machines with Capacity Constraints

Details Approximating Scheduling Machines with Capacity Constraints Approximating Scheduling Machines with Capacity Constraints

2009-06-17

arxiv.org/abs/0906.3056v1

Computer Science

Data Structures and Algorithms

this is a correction of paper to appear at FAW2009

Scientific paper

In the Scheduling Machines with Capacity Constraints problem, we are given k identical machines, each of which can process at most m_i jobs. M jobs are also given, where job j has a non-negative processing time length t_j >= 0. The task is to find a schedule such that the makespan is minimized and the capacity constraints are met. In this paper, we present a 3-approximation algorithm using an extension of Iterative Rounding Method introduced by Jain. To the best of the authors' knowledge, this is the first attempt to apply Iterative Rounding Method to scheduling problem with capacity constraints.

Affiliated with

Also associated with

No associations

Rating

Approximating Scheduling Machines with Capacity Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating Scheduling Machines with Capacity Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating Scheduling Machines with Capacity Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-222170