Parallel machines scheduling to minimize the maximum deviation of the completion times of machines from a common due date

Abstract

The article describes the properties research of the problem of creating a feasible schedule of jobs on parallel machines with a view of minimizing the maximum deviation of the times when the machines complete all the jobs from the due date. Applying the methodology of PDC-algorithms the signs of optimal schedules are developed, which are defined on the basis of the permutations set that allow to consistently improve the value of the criterion. The polynomial component of the PDC-algorithm for the problem solution is developed. Provides an assessment of deviations from the optimum. A practical application of the developed algorithm is considered.