### Аннотация

The object of investigation is the routing open shop problem, in which a fleet of machines have to visit all the nodes of a given transportation network to perform operations on some jobs located at those nodes. Each machine has to visit each node, to process each job and to return back to the common initial location—the depot. Operations of each job can be processed in an arbitrary sequence, any machine may perform at most one operation at a time. The goal is to construct a feasible schedule to minimize the makespan. The routing open shop problem is known to be NP-hard even in the simplest two-machine case with the transportation network consisting of just two nodes (including the depot). We consider a certain generalization of this problem in which travel times are individual for each of the two machines and the structure of the transportation network is an arbitrary cactus. We generalize an instance reduction algorithm known for the problem on a tree with identical travel times, and use it to describe new polynomially solvable cases for the problem, as well as an efficient approximation algorithm for another special case with a tight approximation ratio guarantee.

Язык оригинала | английский |
---|---|

Название основной публикации | Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers |

Редакторы | Milojica Jaćimović, Michael Khachay, Vlasta Malkova, Mikhail Posypkin |

Издатель | Springer Gabler |

Страницы | 1-15 |

Число страниц | 15 |

ISBN (печатное издание) | 9783030386023 |

DOI | |

Состояние | Опубликовано - 1 янв 2020 |

Событие | 10th International Conference on Optimization and Applications, OPTIMA 2019 - Petrovac, Черногория Продолжительность: 30 сен 2019 → 4 окт 2019 |

### Серия публикаций

Название | Communications in Computer and Information Science |
---|---|

Том | 1145 CCIS |

ISSN (печатное издание) | 1865-0929 |

ISSN (электронное издание) | 1865-0937 |

### Конференция

Конференция | 10th International Conference on Optimization and Applications, OPTIMA 2019 |
---|---|

Страна | Черногория |

Город | Petrovac |

Период | 30.09.2019 → 04.10.2019 |

### Fingerprint

### Цитировать

*Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers*(стр. 1-15). (Communications in Computer and Information Science; Том 1145 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-38603-0_1