A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network

DOI10.1016/j.ejor.2003.06.050zbMath1069.90037OpenAlexW2157120658MaRDI QIDQ1779528

Ilya Chernykh, Oded Berman, Igor Averbakh

Publication date: 1 June 2005

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2003.06.050

zbMATH Keywords

Combinatorial optimizationSchedulingApproximation algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Exponential tightness for integral-type functionals of centered independent differently distributed random variables, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass, Two-machine open shop problem with a single server and set-up time considerations, On a routing Open Shop Problem on two nodes with unit processing times, A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times, Approximation algorithms for two-machine proportionate routing open shop on a tree, Routing open shop and flow shop scheduling problems, A survey of scheduling problems with setup times or costs, Four decades of research on the open-shop scheduling problem to minimize the makespan, Irreducible bin packing and normality in routing open shop, Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, The routing open-shop problem on a network: complexity and approximation, Transporting jobs through a two‐machine open shop, A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing, O(log m)-approximation for the routing open shop problem, Two-machine routing open shop: How long is the optimal makespan?

Cites Work

• Unnamed Item
• Unnamed Item
• A heuristic for the two-machine open-shop scheduling problem with transportation times
• Group technology approach to the open shop scheduling problem with batch setup times
• Two-machine shop scheduling problems with batch processing
• Two-machine open shop scheduling with special transportation times
• Open Shop Scheduling to Minimize Finish Time
• Routing Two-Machine Flowshop Problems on Networks with Special Structure
• A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems