Standard

Completing partial schedules for open shop with unit processing times and routing. / Van Bevern, René; Pyatkin, Artem V.

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, 2016. стр. 73-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 9691).

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

Harvard

Van Bevern, R & Pyatkin, AV 2016, Completing partial schedules for open shop with unit processing times and routing. в GJ Woeginger & AS Kulikov (ред.), Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 9691, Springer-Verlag GmbH and Co. KG, стр. 73-87, 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Российская Федерация, 09.06.2016. https://doi.org/10.1007/978-3-319-34171-2_6

APA

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

Vancouver

Van Bevern R, Pyatkin AV. Completing partial schedules for open shop with unit processing times and routing. в Woeginger GJ, Kulikov AS, Редакторы, Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings. Springer-Verlag GmbH and Co. KG. 2016. стр. 73-87. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-34171-2_6

Author

Van Bevern, René ; Pyatkin, Artem V. / Completing partial schedules for open shop with unit processing times and routing. 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, 2016. стр. 73-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{d786ace32139447ca989e38a23890775,
title = "Completing partial schedules for open shop with unit processing times and routing",
abstract = "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{\textquoteright}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.",
keywords = "Edge list-coloring, Fixed-parameter algorithm, NP-hard scheduling problem, Sequence-dependent family or batch setup times",
author = "{Van Bevern}, Ren{\'e} and Pyatkin, {Artem V.}",
year = "2016",
month = jan,
day = "1",
doi = "10.1007/978-3-319-34171-2_6",
language = "English",
isbn = "9783319341705",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "73--87",
editor = "Woeginger, {Gerhard J.} and Kulikov, {Alexander S.}",
booktitle = "Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings",
address = "Germany",
note = "11th International Computer Science Symposium in Russia, CSR 2016 ; Conference date: 09-06-2016 Through 13-06-2016",

}

RIS

TY - GEN

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

AU - Van Bevern, René

AU - Pyatkin, Artem V.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

KW - Edge list-coloring

KW - Fixed-parameter algorithm

KW - NP-hard scheduling problem

KW - Sequence-dependent family or batch setup times

UR - http://www.scopus.com/inward/record.url?scp=84977497417&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-34171-2_6

DO - 10.1007/978-3-319-34171-2_6

M3 - Conference contribution

AN - SCOPUS:84977497417

SN - 9783319341705

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 73

EP - 87

BT - Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings

A2 - Woeginger, Gerhard J.

A2 - Kulikov, Alexander S.

PB - Springer-Verlag GmbH and Co. KG

T2 - 11th International Computer Science Symposium in Russia, CSR 2016

Y2 - 9 June 2016 through 13 June 2016

ER -

ID: 22339648