Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments

DOI10.1016/j.tcs.2019.12.009zbMath1436.90055OpenAlexW3041213598MaRDI QIDQ5919347

Daniel R. Page, Marten Maack, Roberto Solis-Oba

Publication date: 29 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.12.009

zbMATH Keywords

approximation algorithmsrestricted assignmentunrelated parallel machine schedulingbag constraintsbounded job assignmentsjob-intersection graphs

Mathematics Subject Classification ID

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

Related Items (1)

Scheduling High Multiplicity Jobs on Parallel Multi-Purpose Machines with Setup Times and Machine Available Times

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• On the configuration-LP for scheduling on unrelated machines
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Finding and counting given length cycles
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Approximation algorithms for scheduling unrelated parallel machines
• A note on graph balancing problems with restrictions
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Minimizing makespan with release times on identical parallel batching machines
• Structural parameters for scheduling with assignment restrictions
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• Graph balancing: a special case of scheduling unrelated parallel machines
• An optimal rounding gives a better approximation for scheduling unrelated machines
• An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints
• The Design of Approximation Algorithms
• k-cyclic Orientations of Graphs
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Graph Classes: A Survey
• 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
• Parallel machine scheduling with job assignment restrictions
• Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
• Makespan minimization on unrelated parallel machines with a few bags

This page was built for publication: Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments