A linear time approximation algorithm for permutation flow shop scheduling

DOI10.1016/J.TCS.2011.10.013MaRDI QIDQ764320zbMATH OpenOpenAlexFDO

Authors Marcus Poggi, David Sotelo

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

approximation algorithmspermutation flow shop schedulingErdős-Szekeres theorem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Recommendations

• Tight bounds for permutation flow shop scheduling
• Tight Bounds for Permutation Flow Shop Scheduling
• A note on permutation flow shop problem
• An approximation algorithm for the \(m\)-machine permutation flow shop scheduling problem with controllable processing times
• Some results of the worst-case analysis for flow shop scheduling

Cites work

• scientific article; zbMATH DE number 3903967 (Why is no real title available?)
• scientific article; zbMATH DE number 795114 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A note on permutation flow shop problem
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• Approximability of flow shop scheduling
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Flowshop and Jobshop Schedules: Complexity and Approximation
• New results in the worst-case analysis for flow-shop scheduling
• On some geometric methods in scheduling theory: A survey
• Optimal two- and three-stage production schedules with set-up time included
• Partitioning a sequence into few monotone subsequences
• Performance guarantees for flowshop heuristics to minimize makespan
• Permutation vs. non-permutation flow shop schedules
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• The Complexity of Flowshop and Jobshop Scheduling
• Tight Bounds for Permutation Flow Shop Scheduling
• Tight bounds for permutation flow shop scheduling
• Worst-case analysis of Dannenbring's algorithm for flow-shop scheduling
• Worst-case analysis of an approximation algorithm for flow-shop scheduling

Cited in

(8)

• A note on permutation flow shop problem
• A linear time approximation algorithm for movement minimization in conveyor flow shop processing
• scientific article; zbMATH DE number 4130180 (Why is no real title available?)
• Polynomial time algorithms for the UET permutation flowshop problem with time delays
• Tight Bounds for Permutation Flow Shop Scheduling
• scientific article; zbMATH DE number 4089300 (Why is no real title available?)
• Diversity of processing times in permutation flow shop scheduling problems
• Tight bounds for permutation flow shop scheduling

This page was built for publication: A linear time approximation algorithm for permutation flow shop scheduling

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