| Autor: |
Alexander Lazarev, Nikolay Pravdivets, Egor Barashov |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Mathematics, Vol 12, Iss 5, p 699 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2227-7390 |
| DOI: |
10.3390/math12050699 |
| Popis: |
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(n2(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)=1n∑j=1n∣wj−wj0∣wj0, which is an indicator of the average modulus of the relative deviation of the found values wj from the true values wj0. 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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
|
Nepřihlášeným uživatelům se plný text nezobrazuje |
K zobrazení výsledku je třeba se přihlásit.
|
