Open shop scheduling problems with conflict graphs

DOI10.1016/J.DAM.2017.04.031MaRDI QIDQ2357137zbMATH OpenOpenAlexFDO

Authors Mourad Boudhar, Nour El Houda Tellache

Publication date 19 June 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2017.04.031

zbMATH Keywords

complexityconflict graphsheuristicslower boundsmakespanopen shop scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Flow shop scheduling problem with conflict graphs
• New complexity results for shop scheduling problems with agreement graphs
• Scheduling identical jobs on uniform machines with a conflict graph
• Open shop scheduling with some additional constraints
• The representation of partially-concurrent open shop problems

Cites work

• A branch \(\&\) bound algorithm for the open-shop problem
• A note on greedy algorithms for the maximum weighted independent set problem
• A preemptive open shop scheduling problem with one resource
• Addendum: Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
• Classical and new heuristics for the open-shop problem: A computational evaluation
• Constructive heuristic algorithms for the open shop problem
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 4095196 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes. I
• Open Shop Scheduling to Minimize Finish Time
• Reducibility among combinatorial problems
• Scheduling
• Scheduling jobs on identical machines with agreement graph
• Scheduling subject to resource constraints: Classification and complexity
• Scheduling the two-machine open shop problem under resource constraints for setting the jobs
• Scheduling with conflicts: Online and offline algorithms
• Scheduling with incompatible jobs
• Scheduling: agreement graph vs resource constraints
• Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
• Two-Machine Open Shops with Renewable Resources
• Unit-time scheduling problems with time dependent resources

Cited in

(13)

• Flow shop scheduling problem with conflict graphs
• Approximation algorithms for two-machine flow-shop scheduling with a conflict graph
• New complexity results for shop scheduling problems with agreement graphs
• Four decades of research on the open-shop scheduling problem to minimize the makespan
• A metric approach for scheduling problems with minimizing the maximum penalty
• Scheduling identical jobs on uniform machines with a conflict graph
• Two-machine open shop problem with agreement graph
• The representation of partially-concurrent open shop problems
• New results in two identical machines scheduling with agreement graphs
• A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts
• scientific article; zbMATH DE number 4072696 (Why is no real title available?)
• A genetic algorithm for scheduling open shops with conflict graphs to minimize the makespan
• Scheduling on uniform machines with a conflict graph: complexity and resolution

This page was built for publication: Open shop scheduling problems with conflict graphs

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