Решение NP-трудной задачи теории расписаний минимизации суммарного запаздывания
The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n 2Σp j ), where n is the number of jobs and p j is the processing time of the jth job (j = 1, 2, …, n).