An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times

René A. van Bevern, Artem V. Pyatkin, Sergey Sevastyanov

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

For the Routing Open Shop problem with unit execution times, the first algorithm with parameterized complexity is designed for constructing an optimal schedule. Its running time is bounded by a function (Pol(|V|) + f(m, g)) · |I|, where Pol(|V|) is a polynomial of the number of network nodes, f(m; g) is a function of the number of machines and the number of job locations, and |I| is the input length in its compact encoding.

Original languageEnglish
Pages (from-to)42-84
Number of pages43
JournalСибирские электронные математические известия
Volume16
DOIs
Publication statusPublished - 1 Jan 2019

Keywords

  • FPT-algorithm
  • Open Shop problem
  • Parameterized complexity
  • Routing
  • Scheduling
  • UET
  • routing
  • scheduling
  • parameterized complexity
  • SETUP

OECD FOS+WOS

  • 1.01 MATHEMATICS

Access to Document

Fingerprint Dive into the research topics of 'An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times'. Together they form a unique fingerprint.

Cite this