The multiprocessor scheduling problem is defined as follows: jobs have to be executed on several parallel identical processors. Each job has a positive processing time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. We study the case where precedence constrains exist between jobs and preemption on processors is not allowed. The objective is to minimize the time, by which all jobs are done. The problem is NP-hard in the strong sense. The best-known approximation algorithm is the critical path algorithm, which generates the list no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule, in which a processor is kept idle at a time when it could begin processing a job. The paper proposes a 2-1/m approximation inserted idle time algorithm for the multiprocessor scheduling. To illustrate the efficiency of our approach, we compared two algorithms on randomly generated sets of jobs.

Translated title of the contributionПриближенные несписочные алгоритмы для многопроцессорных систем
Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research: Recent Trends
Subtitle of host publication21st International Conference, MOTOR 2022, Petrozavodsk, Russia, July 2–6, 2022, Revised Selected Papers
PublisherSpringer Nature
Pages76-88
ISBN (Electronic)9783031162244
ISBN (Print)9783031162237
DOIs
StatePublished - 2022
EventMathematical Optimization Theory and Operations Research - Петрозаводск, Russian Federation
Duration: 2 Jul 20226 Jul 2022
http://motor2022.krc.karelia.ru/en/section/1

Publication series

NameCommunications in Computer and Information Science
PublisherSpringer Nature
Volume1661
ISSN (Print)1865-0929

Conference

ConferenceMathematical Optimization Theory and Operations Research
Abbreviated titleMOTOR 2022
Country/TerritoryRussian Federation
CityПетрозаводск
Period2/07/226/07/22
Internet address

    Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

    Research areas

  • Approximation algorithm, Critical path, Inserted idle time, Makespan, Parallel identical processors

ID: 106984312