Approximation of the Objective Function of Single-Machine Scheduling Problem.

The problem of the approximation of the coefficients of the objective function of a scheduling problem for a single machine is considered. It is necessary to minimize the total weighted completion times of jobs with unknown weight coefficients when a set of problem instances with known optimal schedules is given. It is shown that the approximation problem can be reduced to finding a solution to a system of linear inequalities for weight coefficients. For the case of simultaneous job release times, a method for solving the corresponding system of inequalities has been developed. Based on it, a polynomial algorithm for finding values of weight coefficients that satisfy the given optimal schedules was constructed. The complexity of the algorithm is O (n 2 (N + n)) operations, where n is the number of jobs and N is the number of given instances with known optimal schedules. The accuracy of the algorithm is estimated by experimentally measuring the function ε (N , n) = 1 n ∑ j = 1 n ∣ w j − w j 0 ∣ w j 0 , which is an indicator of the average modulus of the relative deviation of the found values w j from the true values w j 0 . An analysis of the results shows a high correlation between the dependence ε (N , n) and a function of the form α (n) / N , where α (n) is a decreasing function of n. [ABSTRACT FROM AUTHOR]