TY - GEN

T1 - Approximation and Exact Algorithms for Multiprocessor Scheduling Problem with Release and Delivery Times

AU - Grigoreva, Natalia

N1 - Publisher Copyright: © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2022

Y1 - 2022

N2 - The multiprocessor scheduling problem is defined as follows: set of jobs have to be executed on parallel identical processors. For each job we know release time, processing time and delivery time. At most one job can be performed on every processor at a time, but all jobs may be simultaneously delivered. Preemption on processors is not allowed. The goal is to minimize the time, by which all tasks are delivered. Scheduling tasks among parallel processors is a NP-hard problem in the strong sense. The best known approximation algorithm is Jackson’s algorithm, which generates the list schedule by selecting the ready job with the largest delivery time. This algorithm generates no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor can be idle at a time when it could begin performing a ready job. The paper proposes the approximation inserted idle time algorithm for the multiprocessor scheduling. We proved that deviation of this algorithm from the optimum is smaller then twice the largest processing time. Then by combining the MDT/IIT algorithm and the branch and bound method this paper presents BB algorithm which can find optimal solutions for the problem. To illustrate the efficiency of our approach we compared two algorithms on randomly generated sets of jobs.

AB - The multiprocessor scheduling problem is defined as follows: set of jobs have to be executed on parallel identical processors. For each job we know release time, processing time and delivery time. At most one job can be performed on every processor at a time, but all jobs may be simultaneously delivered. Preemption on processors is not allowed. The goal is to minimize the time, by which all tasks are delivered. Scheduling tasks among parallel processors is a NP-hard problem in the strong sense. The best known approximation algorithm is Jackson’s algorithm, which generates the list schedule by selecting the ready job with the largest delivery time. This algorithm generates no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor can be idle at a time when it could begin performing a ready job. The paper proposes the approximation inserted idle time algorithm for the multiprocessor scheduling. We proved that deviation of this algorithm from the optimum is smaller then twice the largest processing time. Then by combining the MDT/IIT algorithm and the branch and bound method this paper presents BB algorithm which can find optimal solutions for the problem. To illustrate the efficiency of our approach we compared two algorithms on randomly generated sets of jobs.

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

UR - https://www.mendeley.com/catalogue/de1e109c-0758-304e-96fe-1273141ef1af/

U2 - 10.1007/978-3-030-82397-9_7

DO - 10.1007/978-3-030-82397-9_7

M3 - Conference contribution

AN - SCOPUS:85122012266

SN - 9783030823962

T3 - Studies in Computational Intelligence

SP - 139

EP - 156

BT - Recent Advances in Computational Optimization - Results of the Workshop on Computational Optimization WCO 2020

A2 - Fidanova, Stefka

PB - Springer Nature

T2 - Workshops on Computational Optimization, WCO 2020

Y2 - 6 September 2020 through 9 September 2020

ER -