A greedy algorithm for the solution of the classical NP-hard scheduling problem of minimizing the total delay

An efficient method for solving the classical NP-hard problem of scheduling theory for one device—the problem of minimizing the total delay $1||\sum T_{j} $ —is presented. An algorithm for solving the problem is proposed based on the decomposition of the original problem into subproblems of timely servicing each of the requests and placing those of them for which the increase in the delay is most compensated for by the reduction in the delay of the previous requests at the end of the schedules. The complexity of the algorithm does not exceed $O\left (n^{2}\right ) $ operations, where $n$ is the number of requests.