A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job

DOI10.1007/S10951-015-0454-9zbMath1341.90043OpenAlexW2205180844MaRDI QIDQ283266

F. Blanchet-Sadri, M. Dambrine

Publication date: 13 May 2016

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-015-0454-9

zbMATH Keywords

polynomial-time algorithmspreemptionmixed-shop scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• Unnamed Item
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• The mixed shop scheduling problem
• Scheduling two jobs with fixed and nonfixed routes
• How useful are preemptive schedules?
• Shop-scheduling problems with fixed and non-fixed machine orders of the jobs
• Complexity of mixed shop scheduling problems: A survey
• A complete 4-parametric complexity classification of short shop scheduling problems
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• Two-Machine Super-Shop Scheduling Problem
• Open Shop Scheduling to Minimize Finish Time
• Computational Complexity of Discrete Optimization Problems
• The edge chromatic number of a directed/mixed multigraph
• Short Shop Schedules
• On preemption redundancy in scheduling unit processing time jobs on two parallel machines

This page was built for publication: A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job