Scheduling with machine conflicts

DOI10.1007/978-3-031-18367-6_3MaRDI QIDQ6176548zbMATH OpenOpenAlexFDO

Authors Moritz Buchem, Linda Kleist, Daniel Schmidt genannt Waldschmidt

Publication date 25 July 2023

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.08231

zbMATH Keywords

approximation algorithmbipartite graphinapproximabilitymachine conflictNP-hardschedulingstar forest

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Abstract: We study the scheduling problem of makespan minimization while taking machine conflicts into account. Machine conflicts arise in various settings, e.g., shared resources for pre- and post-processing of tasks or spatial restrictions. In this context, each job has a blocking time before and after its processing time, i.e., three parameters. We seek for conflict-free schedules in which the blocking times of no two jobs intersect on conflicting machines. Given a set of jobs, a set of machines, and a graph representing machine conflicts, the problem SchedulingWithMachineConflicts (SMC), asks for a conflict-free schedule of minimum makespan. We show that, unless $extrmP=extrmNP$, SMC on $m$ machines does not allow for a $mathcalO(m^{1-varepsilon})$-approximation algorithm for any $varepsilon>0$, even in the case of identical jobs and every choice of fixed positive parameters, including the unit case. Complementary, we provide approximation algorithms when a suitable collection of independent sets is given. Finally, we present polynomial time algorithms to solve the problem for the case of unit jobs on special graph classes. Most prominently, we solve it for bipartite graphs by using structural insights for conflict graphs of star forests.

Cites work

• A branch-and-price algorithm for the general case of scheduling parallel machines with a single server
• Algorithms for Scheduling Independent Tasks
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• Approximation schemes for scheduling on parallel machines
• Bounded vertex colorings of graphs
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Buffer minimization with conflicts on a line
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Closing the gap for makespan scheduling via sparsification techniques
• Combinatorial optimization. Theory and algorithms
• Complexity results for parallel machine problems with a single server
• Equal processing and equal setup time cases of scheduling parallel machines with a single server
• Equitable colorings of bounded treewidth graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• scientific article; zbMATH DE number 1754640 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes. I
• On minimizing the makespan when some jobs cannot be assigned on the same machine
• On the optimality of approximation schemes for the classical scheduling problem
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parallel machine scheduling problems with a single server
• Parallel machine scheduling with a common server
• Restricted coloring models for timetabling
• Restrictions of graph partition problems. I
• Scheduling master-slave multiprocessor systems
• Scheduling parallel machines with a single server: Some solvable cases and heuristics
• Scheduling self-suspending tasks: new and old results
• Scheduling two parallel machines with a single server: the general case
• Scheduling with incompatible jobs
• Scheduling with machine conflicts
• Single-server parallel-machine scheduling with loading and unloading times
• The approximation of maximum subgraph problems

Cited in

(2)

• scientific article; zbMATH DE number 1082109 (Why is no real title available?)
• Scheduling with machine conflicts

This page was built for publication: Scheduling with machine conflicts

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