Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms

DOI10.1016/j.artint.2022.103711zbMath1493.90067OpenAlexW4223463124WikidataQ114206167 ScholiaQ114206167MaRDI QIDQ2152489

Tytus Pikies, Krzysztof Turowski, Marek Kubale

Publication date: 8 July 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2022.103711

zbMATH Keywords

makespanNP-hardnessuniform machinesjob schedulingapproximation schemetotal completion timeincompatibility graph

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

An improved algorithm for parallel machine scheduling under additional resource constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restrictions of graph partition problems. I
• Approximation algorithms for scheduling unrelated parallel machines
• Class constrained bin packing revisited
• Scheduling with incompatible jobs
• Polynomial time approximation schemes for class-constrained packing problems
• Mutual exclusion scheduling
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Makespan minimization on unrelated parallel machines with a few bags
• Scheduling identical jobs on uniform machines with a conflict graph
• A unified framework for designing EPTAS for load balancing on parallel machines
• A survey of scheduling problems with setup times or costs
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Optimal two- and three-stage production schedules with setup times included
• Scheduling identical jobs on uniform parallel machines
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Scheduling independent tasks to reduce mean finishing time
• On minimizing the makespan when some jobs cannot be assigned on the same machine
• An EPTAS for scheduling on unrelated machines of few different types

This page was built for publication: Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms