A note on worst-case analysis of approximation algorithms for a scheduling problem

DOI10.1016/0377-2217(94)90210-0zbMath0804.90073OpenAlexW2048196919MaRDI QIDQ1330557

Czesław Smutnicki, Eugeniusz Nowicki

Publication date: 19 January 1995

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(94)90210-0

zbMATH Keywords

performance evaluationworst-case analysisapproximation algorithms\(m\)-machine permutation flow-shop

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items

Experimental comparison of heuristics for flow shop scheduling, An empirical analysis of the optimality rate of flow shop heuristics, A fast tabu search algorithm for the permutation flow-shop problem, A new constructive heuristic for the flowshop scheduling problem, Some results of the worst-case analysis for flow shop scheduling, Performance guarantees for flowshop heuristics to minimize makespan

Cites Work

• Unnamed Item
• New results in the worst-case analysis for flow-shop scheduling
• The application of the simulated annealing algorithm to the solution of the \(n/m/C_{\max}\) flowshop problem
• Some efficient heuristic methods for the flow shop sequencing problem
• Worst-case analysis of an approximation algorithm for flow-shop scheduling
• Worst-case analysis of Dannenbring's algorithm for flow-shop scheduling
• A new heuristic for the n-job, M-machine flow-shop problem
• Flowshop and Jobshop Schedules: Complexity and Approximation
• An Evaluation of Flow Shop Sequencing Heuristics
• A Heuristic Algorithm for the n Job, m Machine Sequencing Problem
• A Functional Heuristic Algorithm for the Flowshop Scheduling Problem