Approximating Scheduling Machines with Capacity Constraints

DOI10.1007/978-3-642-02270-8_29MaRDI QIDQ5321720zbMATH OpenOpenAlexFDO

Authors Chi Zhang, Gang Wang, Xiaoguang Liu, Jing Liu

Publication date 14 July 2009

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.3056

zbMATH Keywords

approximationcapacity constraintsiterative roundingscheduling

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Abstract: 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.

Recommendations

• An efficient PTAS for parallel machine scheduling with capacity constraints
• Approximation schemes for scheduling and covering on unrelated machines
• Resource constrained scheduling on multiple machines
• An approximation algorithm for scheduling two parallel machines with capacity constraints.
• An approximation algorithm for the generalized assignment problem

Cites work

• A comment on scheduling two parallel machines with capacity constraints
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• An approximation algorithm for scheduling two parallel machines with capacity constraints.
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximation algorithms for scheduling unrelated parallel machines
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 1875417 (Why is no real title available?)

Cited in

(8)

• Scheduling with limited machine availability
• Busy time scheduling on a bounded number of machines (extended abstract)
• An efficient PTAS for parallel machine scheduling with capacity constraints
• A 3/2-approximation algorithm for k_i-partitioning
• A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width
• Scheduling with cardinality dependent unavailability periods
• Time-sharing scheduling with tolerance capacities
• Makespan minimization for ordinal cardinality constrained scheduling

This page was built for publication: Approximating Scheduling Machines with Capacity Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5321720)