A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing

DOI10.1007/s10951-021-00694-7zbMath1479.90098OpenAlexW3183990372MaRDI QIDQ2059090

Ilya Chernykh, Antonina P. Khramova

Publication date: 13 December 2021

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

Full work available at URL: https://doi.org/10.1007/s10951-021-00694-7

zbMATH Keywords

open shoprouting open shopunrelated travel timespolynomially solvable subcasesproblems with transportation delaysvariable depot

Mathematics Subject Classification ID

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

Related Items (4)

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 ⋮ An FPTAS for scheduling with resource constraints ⋮ Approximation algorithms for two-machine proportionate routing open shop on a tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient approximation algorithms for the routing open shop problem
• Complexity results for flow-shop and open-shop scheduling problems with transportation delays
• The museum visitor routing problem
• A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• Two-machine shop scheduling problems with batch processing
• Routing open shop with two nodes, unit processing times and equal number of jobs and machines
• A cyclical search for the two machine flow shop and open shop to minimise finishing time
• The routing open-shop problem on a network: complexity and approximation
• Two-machine shop scheduling: Compromise between flexibility and makespan value
• An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
• Some positive news on the proportionate open shop problem
• Routing Open Shop with Unrelated Travel Times
• Open Shop Scheduling to Minimize Finish Time
• Short Shop Schedules
• A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems
• O(log m)-approximation for the routing open shop problem
• On the routing open shop problem with two machines on a two-vertex network
• Completing Partial Schedules for Open Shop with Unit Processing Times and Routing

This page was built for publication: A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing