Математическая модель одного класса задач планирования работы независимых машин
Рассмотрен один класс задач теории расписаний. Построена математическая модель задачи планирования работы разнотипных машин с периодами простоя. Сформулирована и доказана теорема о корректности приведения этой задачи к специальной задаче комбинаторной оптимизации. Разработан алгоритм нахождения нижн...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2014 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84816 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Математическая модель одного класса задач планирования работы независимых машин / Л.Ф. Гуляницкий, В.В. Туринский // Компьютерная математика. — 2014. — № 1. — С. 113-118. — Бібліогр.: 2 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860058590551736320 |
|---|---|
| author | Гуляницкий, Л.Ф. Туринский, В.В. |
| author_facet | Гуляницкий, Л.Ф. Туринский, В.В. |
| citation_txt | Математическая модель одного класса задач планирования работы независимых машин / Л.Ф. Гуляницкий, В.В. Туринский // Компьютерная математика. — 2014. — № 1. — С. 113-118. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Рассмотрен один класс задач теории расписаний. Построена математическая модель задачи планирования работы разнотипных машин с периодами простоя. Сформулирована и доказана теорема о корректности приведения этой задачи к специальной задаче комбинаторной оптимизации. Разработан алгоритм нахождения нижней границы целевой функции возникающей задачи оптимизации.
Розглянуто один клас задач теорії розкладів. Побудована математична модель задачі планування роботи різнотипних машин з періодами простою. Сформульована і доведена теорема про коректність приведення цієї задачі до спеціальної задачі комбінаторної оптимізації. Розроблений алгоритм знаходження нижньої межі цільової функції задачі оптимізації, що виникає.
The paper deals with a class of scheduling problems. Mathematical model for the problem of scheduling on a set of unrelated machines with availability constraints is developed. Representation of this problem as a special combinatorial optimization problem is formulated and its correctness is proved. The algorithm for calculating lower bound of objective function of the problem under consideration is developed.
|
| first_indexed | 2025-12-07T17:03:15Z |
| format | Article |
| fulltext |
Компьютерная математика. 2014, № 1 113
Теория и методы
оптимизации
Рассмотрен один класс задач
теории расписаний. Построена
математическая модель задачи
планирования работы разнотип-
ных машин с периодами простоя.
Сформулирована и доказана тео-
рема о корректности приведения
этой задачи к специальной задаче
комбинаторной оптимизации. Раз-
работан алгоритм нахождения
нижней границы целевой функции
возникающей задачи оптимизации.
Л.Ф. Гуляницкий,
В.В. Туринский, 2014
Л.Ф. ГУЛЯНИЦКИЙ, В.В. ТУРИНСКИЙ
114 Компьютерная математика. 2014, № 1
УДК 519.8
Л.Ф. ГУЛЯНИЦКИЙ, В.В.
ТУРИНСКИЙ
МАТЕМАТИЧЕСКАЯ
МОДЕЛЬ ОДНОГО
КЛАССА ЗАДАЧ
ПЛАНИРОВАНИЯ
РАБОТЫ
НЕЗАВИСИМЫХ
МАШИН
Введение. Проблемы
размещения геометри-ческих
объектов являются
актуальными с точки зрения
практики классом задач. В
этот круг входит ряд задач
управления, построе-ния
генеральных планов
предприятий, логистики,
покрытия, оптимального
раскроя промышленных
материалов, некоторые за-дачи
теории расписаний,
диспетчеризации и объемного
календарного планирования и
др.
В работе рассмотрен один
класс задач размещения,
интерпретируемый в
терминах теории расписаний.
Суть проблемы заклю-чается
в распределении множества
работ между заданным
множеством машин, кото-рые
могут выполнять эти работы с
разной производительностью.
В общем случае ма-шины
являются независимыми, т. е.
время выполнения каждой работы на
конкретной машине зависит от номера
данной машины и не связано со временем
выполнения этой работы на других машинах.
Также машины могут иметь промежутки
времени, во время которых планирование
работ запрещено – так называемые периоды
простоя. С прак-тической точки зрения
разные времена выполнения работ можно
объяснить разной производительностью
машин и спецификой выполнения работ на
каждой из машин, а периоды простоя – как
запланированное техническое обслуживание
машин или их занятость для выполнения
каких-либо других, более важных, заданий.
Указанный класс задач является обобщением
задач, рассмотренных в [1, 2].
Л.Ф. ГУЛЯНИЦКИЙ, В.В. ТУРИНСКИЙ
114 Компьютерная математика. 2014, № 1
Формальная модель задачи. Задано множество работ { }iJ , ni ,,1K=
и множество машин { }jM , mj ,,1K= . Время выполнения каждой работы на
каждой из машин определяется матрицей ( )ij n m
x
×
. Также считается заданным
множество периодов простоя { }lH , 1, , ,l k= K вместе с тремя векторами
( )1,..., kβ β , ( )krr ,...,1 , ( )1,..., ,kτ τ которые определяют длительность периода
простоя, номер машины, к которой он относится, и время его начала
соответственно. Решение задачи можно представить двумя векторами –
( )nss ,...,1 и ( )nzz ,...,1 , задающими номер машины, на которой запланирована
работа, и время начала ее выполнения. Исходя из указанных выше обозначений,
формальная модель задачи может быть представлена следующим образом:
0, 1, , , 1, , ,ijx i n j m> = =K K (1)
0, 1, , ,l l kβ > = K (2)
{ }1, , , 1, , ,is m i n∈ =K K (3)
{ }1, , , 1, , ,lr m l k∈ =K K (4)
0, 1, , ,iz i n≥ = K (5)
0, 1, , .l l kτ ≥ = K (6)
Для всех { }ni ,,1K∈ , { }nv ,,1K∈ , таких что i vs s= , :i vz z<
.
ii is vz x z+ ≤ (7)
Для всех { }ni ,,1K∈ , { }kv ,,1K∈ , таких что i vs r= , :i vz < τ
.
ii is vz x+ ≤ τ (8)
Для всех { }ni ,,1K∈ , { }kv ,,1K∈ , таких что vi rs = , :v izτ <
,v v izτ + β ≤ (9)
1, ,
max( ) min.
ii is
i n
z x
=
+ →
K
(10)
Ограничение (7) задает непересечение запланированных работ на одной
машине, ограничения (8) и (9) – непересечение работ и периодов простоя.
Ограничение (10) – целевая функция задачи, которая обеспечивает минимиза-
цию времени завершения наиболее поздней работы (т. н. гильотинный раскрой).
Формализация задачи в пространстве перестановок. Учитывая специ-
фику приведенных ограничений и возникающих на практике размерностях,
решение задач традиционными методами нелинейного программирования
нерационально и чаще всего неэффективно. Поэтому целесообразно рассмотреть
данную задачу в терминах комбинаторной оптимизации.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОДНОГО КЛАССА ЗАДАЧ ПЛАНИРОВАНИЯ…
Компьютерная математика. 2014, № 1 115
Как указано ранее, решение задачи однозначно определяется парой векторов
( )zsR , , где ( ) ( )nn zzzsss ,...,,,..., 11 == , которому соответствует значение
целевой функции
1, ,
( ( , )) max ( )
ii is
i n
F R s z z x
=
= +
K
. Рассмотрим пространство
перестановок ( ) { }{ }1,..., : 1,..., , , ; , 1,...,n n i i jP p p p p n p p i j i j n= = ∈ ≠ ≠ = ,
где каждая перестановка является последовательностью из неповторяющихся
номеров работ. Предложим алгоритм, который каждой перестановке из
множества nP ставит в соответствие определенное решение из ( ){ , }R R s z= .
Алгоритм 1. Шаг ),,1( nii K= . К текущему плану для машины
ips
добавить работу с номером ip и временем начала
ipz . Пусть {( ,
j jp pT s z= +
), 1,..., 1} {( , ), 1,..., } {( ,0) : 0;
j p j
p s j j j k kx j i r j k j s j z+ = − ∪ τ + β = ∪ ≠ ∨ ≠
1, ..., 1; 1, ..., }k i j m= − = – моменты окончания работ и периодов простоя, а
также моменты начала работы машин, если они не заняты работами. Тогда
' : '
( , ) min{( ', ') : " ' , " min{ '}},
i i i
j
p p p s j
T j s s
s z s z z z x z z z
=
= − ≥ = > т. е. наиболее ранняя
точка на оси времени, где можно запланировать работу, выбирая машину
с меньшим номером при наличии нескольких точек с одинаковым временем.
Докажем корректность перехода к задаче комбинаторной оптимизации,
т. е. что при переходе от бесконечного множества решений R с помощью
указанного алгоритма к конечному пространству перестановок nP оптимальное
решение не теряется.
Теорема. Для любой задачи вида (1) – (10) существует перестановка
( )npp ,...,1 , которой соответствует решение ( )zsR , , построенное по алгоритму
1, являющееся глобальным оптимумом этой задачи.
Доказательство. Очевидно, что в оптимальном решении нет промежутков
между работами и между началом плана и первой работой, запланированной на
машине. При наличии таких промежутков работу всегда можно запланировать
ранее, не увеличив целевую функцию. Промежутки возможны только между
концом работы и началом периода простоя. Рассмотрим такое конечное
множество решений 'R R⊂ , в котором отсутствуют указанные виды
промежутков. Очевидно, что оптимальное решение входит во множество 'R .
Покажем, что любому решению ( ) ',* RzsR ∈ соответствует перестановка
из множества nP . Возьмем за перестановку порядок работ, полученный путем
упорядочивания работ в решении *R по значениям
*
iz , а при их равенстве –
по *.is
Л.Ф. ГУЛЯНИЦКИЙ, В.В. ТУРИНСКИЙ
116 Компьютерная математика. 2014, № 1
Теперь применим алгоритм 1 к данной перестановке, чтобы получить
решение **.R На i-м шаге алгоритма 1 находится точка для размещения работы
)','( zs . Возможны два варианта:
– найденная алгоритмом точка соответствует положению работы в изна-
чальном решении *R и равна * *' , ' ;i is s z z= =
– выполняются условия:
' ,
iisb z x− ≥ 1,..., :j n= 'js s= ⇒ ' jz z> ∨ ' .
iis jz x z+ <
В таком случае также справедливы неравенства * *' , ' .i is s z z< ≠
Вследствие варьирующейся длинны работ, полученное решение **R будет
отличаться от начального решения *R непредсказуемым образом. Но в таком
случае это начальное решение можно преобразовать следующим образом.
** **', ';i is s z z= = * ** *( ') : .
ij j j isj s s z z x∀ = = − Здесь мы перемещаем работу на
свободное место и сдвигаем остальные работы на этой машине влево, если им не
мешают периоды недоступности. Значение целевой функции либо не меняется,
либо становится меньше. Нетрудно увидеть, что это решение тоже принадлежит
множеству ' .R Повторяем процедуру перехода к перестановке и обратно
еще раз.
В итоге мы придем к решению *(.,.)tR , для которого справедливо
неравенство * *( (.,.)) ( (.,.))tF R F R≤ , и перестановке ,tp превращение в кото-
рую и обратно дает исходное решение.
Тогда задачу (1) – (10) можно сформулировать в пространстве перестановок
следующим образом:
найти такую перестановку * np P∈ , что
* arg min ( )
np P
p f p
∈
= , (11)
где ( )( )*** ,)( zsRFpf = .
Алгоритм построения нижней границы. Наличие точной нижней границы
целевой функции задачи дает возможность не только оценивать и сравнивать
результаты работы приближенных алгоритмов, но и останавливать работу
алгоритмов при достижении текущим наилучшим решением определенного
порога. Многие задачи имеют ландшафт, в котором существует множество
локальных оптимумов, которые незначительно хуже глобального. Поиск
глобального оптимума в таком случае не оправдан, и завершение работы
алгоритма при нахождении решения, достаточно близкого к оптимальному,
может значительно улучшить его временные характеристики.
Предлагается следующий алгоритм построения нижней границы для целе-
вой функции сформулированной задачи (11).
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОДНОГО КЛАССА ЗАДАЧ ПЛАНИРОВАНИЯ…
Компьютерная математика. 2014, № 1 117
Алгоритм 2. 1. Формируем множество свободных временных участков для
каждой из машин:
{ }[ , ] : 0 ; }, 1,...,j j j j j j j
j i i i i i l l i l iF f a b a a b b j m= = = ∨ = τ + β = τ ∨ = ∞ = .
2. Удаляем из каждого множества свободных участков те, что удовлетво-
ряют условию: , 1,..., , 1,..., .i i ijb a x i n j m− < = = Очевидно, что в эти времен-
ные участки не поместится ни одна из имеющихся работ.
3.Для каждой работы находим ее минимальную длительность выполнения
на всех машинах:
min
1,...,
min { }, 1,..., .i ij
j m
x x i n
=
= =
Определяем значение
min
1
.
n
total i
i
x x
=
=∑
4. Выбираем шаг ,d с которым будем заполнять расписание. При 0→d
получим искомое значение нижней границы. На практике, однако, можно брать
достаточно малое значение .d В худшем случае, полученное значение нижней
границы будет отличаться от искомого в меньшую сторону на величину .d
5. Находим наиболее ранний свободный временной участок:
1,...,
min {min{ }}.
j
j
t i
j m F
f a
=
=
6. Помещаем туда часть работ, имеющих длительность ' min( , ),t td d b a= −
при этом ' 'total totalx x d= − и '' daa tt += . Если после этого tt ba =' ,
то tjj fFF \'= .
7. Если ' 0,totalx = то алгоритм завершен и нижняя граница равна послед-
нему значению ta , иначе перейти на п. 5.
Заключение. Рассмотрен важный класс задач теории расписаний по
планированию работы независимых машин разной производительности при
наличии заданных периодов простоя. Проблема естественным образом
формулируется в виде специальной задачи нелинейного программирования.
Однако сложность уравнений, возникающих при решении задач практической
размерности, делает неэффективным применение для ее решения традиционных
методов нелинейного программирования. Предложен подход, позволяющий
перейти от сформулированной задачи нелинейного программирования (1) – (10)
к соответствующей задаче комбинаторной оптимизации на перестановках (11).
Доказана теорема, обосновывающая корректность такого перехода. Таким
образом, это открывает возможности применения известных алгоритмов и
методов комбинаторной оптимизации. Также предложен алгоритм построения
нижней границы целевой функции задачи, позволяющая оценивать полученные
приближенные решения и вводить дополнительные критерии остановки
алгоритмов по достижению требуемой точности.
Л.Ф. ГУЛЯНИЦКИЙ, В.В. ТУРИНСКИЙ
118 Компьютерная математика. 2014, № 1
Л.Ф. Гуляницький, В.В. Турінський
МАТЕМАТИЧНА МОДЕЛЬ ОДНОГО КЛАСУ ЗАДАЧ ПЛАНУВАННЯ РОБОТИ
НЕЗАЛЕЖНИХ МАШИН
Розглянуто один клас задач теорії розкладів. Побудована математична модель задачі
планування роботи різнотипних машин з періодами простою. Сформульована і доведена
теорема про коректність приведення цієї задачі до спеціальної задачі комбінаторної
оптимізації. Розроблений алгоритм знаходження нижньої межі цільової функції задачі
оптимізації, що виникає.
L.F. Hulianytskyi, V.V. Turinsky
MATHEMATICAL MODEL FOR A CLASS OF SCHEDULING PROBLEMS
WITH UNRELATED MACHINES
The paper deals with a class of scheduling problems. Mathematical model for the problem of
scheduling on a set of unrelated machines with availability constraints is developed. Representation
of this problem as a special combinatorial optimization problem is formulated and its correctness is
proved. The algorithm for calculating lower bound of objective function of the problem under
consideration is developed.
1. Сергиенко И.В., Гуляницкий Л.Ф., Малышко С.А. О решении задач размещения одного
класса // Экономика и математические методы. –1989. – Том XXV, № 3. – С. 560 – 564.
2. Гуляницкий Л.Ф., Гобов Д.А. О сравнении эффективности алгоритмов решения одного
класса задач размещения прямоугольников на полубесконечной ленте // Компьютерная
математика. – 2003. – № 1. – С. 88 – 97.
Получено 25.12.2013
Об авторах:
Гуляницкий Леонид Федорович,
доктор технических наук, заведующий отделом
Института кибернетики имени В.М. Глушкова НАН Украины,
Е-mail: leonhul.icyb@gmail.com
Туринский Виталий Викторович,
аспирант Института кибернетики имени В.М. Глушкова НАН Украины.
Е-mail: vitaly.turinsky@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-84816 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T17:03:15Z |
| publishDate | 2014 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Гуляницкий, Л.Ф. Туринский, В.В. 2015-07-15T20:04:54Z 2015-07-15T20:04:54Z 2014 Математическая модель одного класса задач планирования работы независимых машин / Л.Ф. Гуляницкий, В.В. Туринский // Компьютерная математика. — 2014. — № 1. — С. 113-118. — Бібліогр.: 2 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84816 519.8 Рассмотрен один класс задач теории расписаний. Построена математическая модель задачи планирования работы разнотипных машин с периодами простоя. Сформулирована и доказана теорема о корректности приведения этой задачи к специальной задаче комбинаторной оптимизации. Разработан алгоритм нахождения нижней границы целевой функции возникающей задачи оптимизации. Розглянуто один клас задач теорії розкладів. Побудована математична модель задачі планування роботи різнотипних машин з періодами простою. Сформульована і доведена теорема про коректність приведення цієї задачі до спеціальної задачі комбінаторної оптимізації. Розроблений алгоритм знаходження нижньої межі цільової функції задачі оптимізації, що виникає. The paper deals with a class of scheduling problems. Mathematical model for the problem of scheduling on a set of unrelated machines with availability constraints is developed. Representation of this problem as a special combinatorial optimization problem is formulated and its correctness is proved. The algorithm for calculating lower bound of objective function of the problem under consideration is developed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Математическая модель одного класса задач планирования работы независимых машин Математична модель одного класу задач планування роботи незалежних машин Mathematical model for a class of scheduling problems with unrelated machines Article published earlier |
| spellingShingle | Математическая модель одного класса задач планирования работы независимых машин Гуляницкий, Л.Ф. Туринский, В.В. Теория и методы оптимизации |
| title | Математическая модель одного класса задач планирования работы независимых машин |
| title_alt | Математична модель одного класу задач планування роботи незалежних машин Mathematical model for a class of scheduling problems with unrelated machines |
| title_full | Математическая модель одного класса задач планирования работы независимых машин |
| title_fullStr | Математическая модель одного класса задач планирования работы независимых машин |
| title_full_unstemmed | Математическая модель одного класса задач планирования работы независимых машин |
| title_short | Математическая модель одного класса задач планирования работы независимых машин |
| title_sort | математическая модель одного класса задач планирования работы независимых машин |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84816 |
| work_keys_str_mv | AT gulânickiilf matematičeskaâmodelʹodnogoklassazadačplanirovaniârabotynezavisimyhmašin AT turinskiivv matematičeskaâmodelʹodnogoklassazadačplanirovaniârabotynezavisimyhmašin AT gulânickiilf matematičnamodelʹodnogoklasuzadačplanuvannârobotinezaležnihmašin AT turinskiivv matematičnamodelʹodnogoklasuzadačplanuvannârobotinezaležnihmašin AT gulânickiilf mathematicalmodelforaclassofschedulingproblemswithunrelatedmachines AT turinskiivv mathematicalmodelforaclassofschedulingproblemswithunrelatedmachines |