Approximation algorithms for job scheduling with block-type conflict graphs

DOI10.1016/J.COR.2024.106606MaRDI QIDQ6568400zbMATH OpenFDO

Authors Hanna Furmańczyk, Tytus Pikies, Inka Sokołowska, Krzysztof Turowski

Publication date 8 July 2024

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COR.2024.106606

zbMATH Keywords

block graphconflict graphidentical machineincompatibility graphschedulinguniform machineunrelated machine

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites work

• A Characterization of Block-Graphs
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A unified framework for designing EPTAS for load balancing on parallel machines
• An exact algorithm for parallel machine scheduling with conflicts
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Bounds for Certain Multiprocessing Anomalies
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 3757695 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 7058467 (Why is no real title available?)
• Makespan minimization on unrelated parallel machines with a few bags
• Max flows in O(nm) time, or better
• Maximum flows by incremental breadth-first search
• Mutual exclusion scheduling
• On minimizing the makespan when some jobs cannot be assigned on the same machine
• Parameterized algorithms
• Scheduling identical jobs on uniform machines with a conflict graph
• Scheduling identical jobs on uniform parallel machines
• Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms
• Scheduling with incompatible jobs

Cited in

(1)

• Compact formulations and valid inequalities for parallel machine scheduling with conflicts

This page was built for publication: Approximation algorithms for job scheduling with block-type conflict graphs

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