Practical Applicability of the Metric Approach for a Scheduling Problem

Authors

  • Alexander Lazarev V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow, Russia https://orcid.org/0000-0003-0979-8189
  • Darya Lemtyuzhnikova V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow, Russia; Moscow Aviation Institute, Moscow, Russia https://orcid.org/0000-0002-5311-5552
  • Ilja Kudinov V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow, Russia

DOI:

https://doi.org/10.25728/assa.2024.2024.02.1597

Keywords:

Scheduling, Optimization and Control, Operations Research, Makespan

Abstract

A given special case of NP-complete scheduling problem can be approximated by solving a special case of similar problem with the same precedence graph. We construct a metric space over a set of special cases of this problem and consider the statistical relationship between distance between a pair of special cases of the under consideration and the average error of the approximated solution. Sethi, Gabow, Coffman's and Fujii's algorithms for this problem are used. It is shown that the absolute and the relative error of the objective function decreases over the density of a graph with a fixed number of jobs. In general case, relative non-zero error value increases with the number of jobs.

Downloads

Download data is not yet available.

Downloads

Published

2024-07-15

How to Cite

Lazarev, A., Lemtyuzhnikova, D., & Kudinov, I. (2024). Practical Applicability of the Metric Approach for a Scheduling Problem. Advances in Systems Science and Applications, 24(02), 94–102. https://doi.org/10.25728/assa.2024.2024.02.1597

Most read articles by the same author(s)