The lexicographical criterion minimization for a feasible schedule on parallel machines with arbitrary due dates
Zgurovskiy M.Z., Pavlov A.A., Misura E.B.
In the paper the PDC-algorithms are developed for scheduling problems of processing independent jobs with due dates on parallel machines with equal and different performance ratios with the vector (lexicographical) or scalar criterion of maximization the minimum moment of the processing start on machines. On the basis of previously created signs of optimality of the feasible solutions the algorithms are developed that implement the polynomial component of the PDC-algorithm and polynomial approximation of exact algorithm for the problems solution – heuristic or approximate algorithms with the estimate of deviation from the optimal solution.
