Completing partial schedules for Open Shop with unit processing times and routing. van Bevern, R. & Pyatkin, A. V. In Kulikov, A. S. & Woeginger, G. J., editors, CSR 2016, volume 9691, of Lecture Notes in Computer Science, pages 73-87. Springer, 2016. ![Completing partial schedules for Open Shop with unit processing times and routing [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Slides doi abstract bibtex 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 J_i∈J on each machine M_q∈M for a given amount p_iq 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. Routing Open Shop is NP-hard for |V|=|M|=2. For the special case of unit processing times p_iq=1, we exploit Galvin's theorem about list-coloring 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 2^O(|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.
@incollection{BP16,
title = {Completing partial schedules for Open Shop with unit
processing times and routing},
doi = {10.1007/978-3-319-34171-2_6},
author = {René van Bevern and Artem V. Pyatkin},
url_Slides = {http://rvb.su/pdf/routing-open-shop-csr16.pdf},
isbn = {978-3-319-34170-5},
year = {2016},
date = {2016-05-31},
booktitle = {CSR 2016},
editor = {Alexander S. Kulikov and Gerhard J. Woeginger},
volume = {9691},
pages = {73-87},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
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 J_i∈J
on each machine M_q∈M for a given amount p_iq 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. Routing Open Shop is NP-hard for
|V|=|M|=2. For the special case of unit processing
times p_iq=1, we exploit Galvin's theorem about
list-coloring 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 2^O(|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 = {NP-hard, parameterized complexity, routing,
scheduling}
}
Downloads: 0
{"_id":"oCyFR3z9FiT4wxJTZ","bibbaseid":"vanbevern-pyatkin-completingpartialschedulesforopenshopwithunitprocessingtimesandrouting-2016","downloads":0,"creationDate":"2016-03-07T11:48:39.117Z","title":"Completing partial schedules for Open Shop with unit processing times and routing","author_short":["van Bevern, R.","Pyatkin, A. V."],"year":2016,"bibtype":"incollection","biburl":"http://rvb.su/rvb.bib","bibdata":{"bibtype":"incollection","type":"incollection","title":"Completing partial schedules for Open Shop with unit processing times and routing","doi":"10.1007/978-3-319-34171-2_6","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Artem","V."],"propositions":[],"lastnames":["Pyatkin"],"suffixes":[]}],"url_slides":"http://rvb.su/pdf/routing-open-shop-csr16.pdf","isbn":"978-3-319-34170-5","year":"2016","date":"2016-05-31","booktitle":"CSR 2016","editor":[{"firstnames":["Alexander","S."],"propositions":[],"lastnames":["Kulikov"],"suffixes":[]},{"firstnames":["Gerhard","J."],"propositions":[],"lastnames":["Woeginger"],"suffixes":[]}],"volume":"9691","pages":"73-87","publisher":"Springer","series":"Lecture Notes in Computer Science","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 J_i∈J on each machine M_q∈M for a given amount p_iq 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. Routing Open Shop is NP-hard for |V|=|M|=2. For the special case of unit processing times p_iq=1, we exploit Galvin's theorem about list-coloring 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 2^O(|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":"NP-hard, parameterized complexity, routing, scheduling","bibtex":"@incollection{BP16,\n title =\t {Completing partial schedules for Open Shop with unit\n processing times and routing},\n doi =\t\t {10.1007/978-3-319-34171-2_6},\n author =\t {René van Bevern and Artem V. Pyatkin},\n url_Slides =\t {http://rvb.su/pdf/routing-open-shop-csr16.pdf},\n isbn =\t {978-3-319-34170-5},\n year =\t {2016},\n date =\t {2016-05-31},\n booktitle =\t {CSR 2016},\n editor =\t {Alexander S. Kulikov and Gerhard J. Woeginger},\n volume =\t {9691},\n pages =\t {73-87},\n publisher =\t {Springer},\n series =\t {Lecture Notes in Computer Science},\n abstract =\t {Open Shop is a classical scheduling problem: given a\n set J of jobs and a set M of machines, find a\n minimum-makespan schedule to process each job J_i∈J\n on each machine M_q∈M for a given amount p_iq of\n time such that each machine processes only one job\n at a time and each job is processed by only one\n machine at a time. In Routing Open Shop, the jobs\n are located in the vertices of an edge-weighted\n graph G=(V,E) whose edge weights determine the time\n needed for the machines to travel between\n jobs. Routing Open Shop is NP-hard for\n |V|=|M|=2. For the special case of unit processing\n times p_iq=1, we exploit Galvin's theorem about\n list-coloring edges of bipartite graphs to prove a\n theorem that gives a sufficient condition for the\n completability of partial schedules. Exploiting this\n schedule completion theorem and integer linear\n programming, we show that Routing Open Shop with\n unit processing times is solvable in 2^O(|V||M|^2\n log |V||M|) poly(|J|)) time, that is,\n fixed-parameter tractable parameterized by\n |V|+|M|. Various upper bounds shown using the\n schedule completion theorem suggest it to be\n likewise beneficial for the development of\n approximation algorithms.},\n keywords =\t {NP-hard, parameterized complexity, routing,\n scheduling}\n}\n\n\n","author_short":["van Bevern, R.","Pyatkin, A. V."],"editor_short":["Kulikov, A. S.","Woeginger, G. J."],"key":"BP16","id":"BP16","bibbaseid":"vanbevern-pyatkin-completingpartialschedulesforopenshopwithunitprocessingtimesandrouting-2016","role":"author","urls":{" slides":"http://rvb.su/pdf/routing-open-shop-csr16.pdf"},"keyword":["NP-hard","parameterized complexity","routing","scheduling"],"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":0,"html":""},"search_terms":["completing","partial","schedules","open","shop","unit","processing","times","routing","van bevern","pyatkin"],"keywords":["np-hard","parameterized complexity","routing","scheduling"],"authorIDs":["2fwXJtKDCNhaSNr5s","56dd6a97e8d527c5470000fa"],"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}