The total tardiness minimization when processing independent tasks with a common due date on the identical parallel machines with an arbitrary starting times

The problem of scheduling independent tasks with a common due date and equal weights in the case of arbitrary starting times of machines is considered. The PDC-algorithm to solve it is proposed. The optimality signs of the polynomial component of the algorithm are formulated. The upper bound of deviation of a solution from optimum is obtained. An example of the problem solution is given.Рассматривается задача составления расписания выполнения независимых заданий с общим директивным сроком и равными весами при произвольных моментах запуска приборов. Предложен ПДС-алгоритм решения задачи, сформулированы признаки оптимальности полиномиальной составляющей алгоритма, получена оценка отклонения получаемых решений от оптимального. Приведен пример решения задачи