Completing partial schedules for open shop with unit processing times and routing

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

6 Цитирования (Scopus)

Аннотация

Open Shop is a classical scheduling problem: given a set J of jobs and a set M of machines, find a minimum-makespan schedule to process each job Ji ∈ J on each machine Mq ∈ M for a given amount piq of time such that each machine processes only one job at a time and each job is processed by only one machine at a time. In Routing Open Shop, the jobs are located in the vertices of an edge-weighted graph G = (V,E) whose edge weights determine the time needed for the machines to travel between jobs. The travel times also have a natural interpretation as sequence-dependent family setup times. Routing Open Shop is NP-hard for |V | = |M| = 2. For the special case with unit processing times piq = 1, we exploit Galvin’s theorem about listcoloring edges of bipartite graphs to prove a theorem that gives a sufficient condition for the completability of partial schedules. Exploiting this schedule completion theorem and integer linear programming, we show that Routing Open Shop with unit processing times is solvable in 2O(|V ||M|2 log |V ||M|) ·poly(|J |) time, that is, fixed-parameter tractable parameterized by |V | + |M|. Various upper bounds shown using the schedule completion theorem suggest it to be likewise beneficial for the development of approximation algorithms.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings
РедакторыGerhard J. Woeginger, Alexander S. Kulikov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы73-87
Число страниц15
ISBN (печатное издание)9783319341705
DOI
СостояниеОпубликовано - 1 янв 2016
Событие11th International Computer Science Symposium in Russia, CSR 2016 - St. Petersburg, Российская Федерация
Продолжительность: 9 июн 201613 июн 2016

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

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9691
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция11th International Computer Science Symposium in Russia, CSR 2016
СтранаРоссийская Федерация
ГородSt. Petersburg
Период09.06.201613.06.2016

ГРНТИ

  • 27 МАТЕМАТИКА

Fingerprint Подробные сведения о темах исследования «Completing partial schedules for open shop with unit processing times and routing». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Van Bevern, R., & Pyatkin, A. V. (2016). Completing partial schedules for open shop with unit processing times and routing. В G. J. Woeginger, & A. S. Kulikov (Ред.), Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings (стр. 73-87). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 9691). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-34171-2_6