The 2-valued case of makespan minimization with assignment constraints

DOI10.1016/J.IPL.2012.09.004MaRDI QIDQ1941692zbMATH OpenOpenAlexFDO

Authors Stavros G. Kolliopoulos, Yannis Moysoglou

Publication date 21 March 2013

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsschedulingmakespan minimizationgraph balancing

Mathematics Subject Classification ID

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

Abstract: We consider the following special case of minimizing makespan. A set of jobs $J$ and a set of machines $M$ are given. Each job $jinJ$ can be scheduled on a machine from a subset $M_j$ of $M$. The processing time of $j$ is the same on all machines in $M_j.$ The jobs are of two sizes, namely $b$ (big) and $s$ (small). We present a polynomial-time algorithm that approximates the value of the optimal makespan within a factor of 1.883 and some further improvements when every job can be scheduled on at most two machines.

Recommendations

• Estimating the makespan of the two-valued restricted assignment problem
• Estimating the makespan of the two-valued restricted assignment problem
• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• On minimizing the makespan when some jobs cannot be assigned on the same machine
• On some special cases of the restricted assignment problem

Cited in

(7)

• On some special cases of the restricted assignment problem
• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Estimating the makespan of the two-valued restricted assignment problem
• Integrality gaps for strengthened linear relaxations of capacitated facility location
• Makespan minimization on unrelated parallel machines with a few bags
• Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs
• Approximation algorithms for the graph balancing problem with two speeds and two job lengths

This page was built for publication: The 2-valued case of makespan minimization with assignment constraints

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