A linear time approximation algorithm for permutation flow shop scheduling

DOI10.1016/j.tcs.2011.10.013zbMath1234.68467MaRDI QIDQ764320

David Sotelo, Marcus Poggi

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.10.013

zbMATH Keywords

Erdős-Szekeres theorem; approximation algorithms; permutation flow shop scheduling

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B35: Deterministic scheduling theory in operations research

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on permutation flow shop problem
• New results in the worst-case analysis for flow-shop scheduling
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Worst-case analysis of an approximation algorithm for flow-shop scheduling
• Partitioning a sequence into few monotone subsequences
• Permutation vs. non-permutation flow shop schedules
• Worst-case analysis of Dannenbring's algorithm for flow-shop scheduling
• Approximability of flow shop scheduling
• On some geometric methods in scheduling theory: A survey
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Performance guarantees for flowshop heuristics to minimize makespan
• Optimal two- and three-stage production schedules with setup times included
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• Flowshop and Jobshop Schedules: Complexity and Approximation
• The Complexity of Flowshop and Jobshop Scheduling
• Tight Bounds for Permutation Flow Shop Scheduling
• Tight Bounds for Permutation Flow Shop Scheduling