Makespan minimization on unrelated parallel machines with a few bags
From MaRDI portal
Publication:2173300
DOI10.1016/j.tcs.2020.03.013zbMath1436.90053OpenAlexW3021772469MaRDI QIDQ2173300
Daniel R. Page, Roberto Solis-Oba
Publication date: 22 April 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.03.013
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)
Related Items (4)
Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts ⋮ Scheduling on uniform machines with a conflict graph: complexity and resolution ⋮ An improved algorithm for parallel machine scheduling under additional resource constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Approximating the multi-level bottleneck assignment problem
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- Approximation algorithms for scheduling unrelated parallel machines
- Scheduling with conflicts: Online and offline algorithms
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Scheduling with incompatible jobs
- Parallel machine scheduling of machine-dependent jobs with unit-length.
- A 3/2-approximation algorithm for the graph balancing problem with two weights
- Estimating the makespan of the two-valued restricted assignment problem
- The 2-valued case of makespan minimization with assignment constraints
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- A quasi-polynomial approximation for the restricted assignment problem
- Approximation algorithms for the graph balancing problem with two speeds and two job lengths
- An optimal rounding gives a better approximation for scheduling unrelated machines
- Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- On the Configuration-LP of the Restricted Assignment Problem
- A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
- On minimizing the makespan when some jobs cannot be assigned on the same machine
- On (1,∊)-Restricted Assignment Makespan Minimization
- A PTAS for Scheduling Unrelated Machines of Few Different Types
- An EPTAS for scheduling on unrelated machines of few different types
- Makespan minimization on unrelated parallel machines with a few bags
This page was built for publication: Makespan minimization on unrelated parallel machines with a few bags
