On minimizing the makespan when some jobs cannot be assigned on the same machine

DOI10.4230/LIPIcs.ESA.2017.31zbMath1442.90071OpenAlexW2759616628MaRDI QIDQ5111718

Andreas Wiese, Syamantak Das

Publication date: 27 May 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2017.31

zbMATH Keywords

schedulingmakespan minimizationapproximation algorithms

Mathematics Subject Classification ID

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

Related Items (8)

An APTAS for bin packing with clique-graph conflicts ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Makespan minimization on unrelated parallel machines with a few bags ⋮ Multi-level bottleneck assignment problems: complexity and sparsity-exploiting formulations ⋮ Scheduling with machine conflicts ⋮ Scheduling on uniform machines with a conflict graph: complexity and resolution ⋮ An improved algorithm for parallel machine scheduling under additional resource constraints ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the multi-level bottleneck assignment problem
• On the configuration-LP for scheduling on unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• Scheduling with conflicts: Online and offline algorithms
• Scheduling with incompatible jobs
• Bin packing with restricted piece sizes
• A quasi-polynomial approximation for the restricted assignment problem
• Graph balancing: a special case of scheduling unrelated parallel machines
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods
• Santa Claus Schedules Jobs on Unrelated Machines
• On (1,∊)-Restricted Assignment Makespan Minimization
• Estimating The Makespan of The Two-Valued Restricted Assignment Problem
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: On minimizing the makespan when some jobs cannot be assigned on the same machine