1. Science
  2. Publications
  3. Information Processing Systems
  4. 1(117)'2014
  5. On the optimality properties of a method to minimize total tardiness on a single machine based on the rank approach and the dominance rules

On the optimality properties of a method to minimize total tardiness on a single machine based on the rank approach and the dominance rules

S.V. Minukhin
Annotations languages:

The method of minimizing the total delay work on the single device pivoted to the problem of finding the shortest Hamiltonian path in a random fully connected graph based on the rank approach and the dominance rules is considered. The properties of an optimal method based on the introduced definitions of locally optimal solutions for the optimal schedule on the rank and the optimality of the final schedule are considered. Definitions and propositions that define the optimality of job schedules on the basis of strictly dominant and dominant schedules for the weighted and unweighted cases are formulated. Metrics evaluation to improve the results of the algorithm using the dominance rules are proposed. The results of computer simulation for estimating improvement of the algorithm, confirming the expediency of the dominance rules.
Keywords: schedule, job, rank approach, dominance rule, metric, graph