|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ФИЦ ПХФ и МХ РАН |
||
Approximation of the Objective Function of Single-Machine Scheduling Problemстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 11 декабря 2024 г.
- Авторы: Lazarev Alexander, Pravdivets Nikolay, Barashov Egor
- Журнал: Mathematics
- Том: 12
- Номер: 5
- Год издания: 2024
- Издательство: MDPI
- Местоположение издательства: Basel, Switzerland
- Первая страница: 699
- Последняя страница: 699
- DOI: 10.3390/math12050699
- Аннотация: 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) = 1 ∑n |wj −w0j | , which is n j=1 w0j an indicator of the average modulus of the relative deviation of the found values wj from the true values w0j . 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
- Добавил в систему: Лазарев Александр Алексеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Снимок_экрана_2024-03-01_в_20.00.36__копия.png | Снимок_экрана_2024-03-01_в_20.00.36__копия.png | 1,2 МБ | 10 декабря 2024 [Lazarev] | |
| 2. | 74625-76546_1.pdf | 74625-76546_1.pdf | 517,6 КБ | 10 декабря 2024 [Lazarev] |