РЕЛАКСАЦИЯ ДИРЕКТИВНЫХ СРОКОВ ПРИ ПОСТРОЕНИИ РАСПИСАНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ ОДНИМ ПРИБОРОМ
Abstract
Рассматривается задача построения расписания обслуживания одним прибором требований
нескольких типов при наличии директивных сроков. Минимизируется взвешенная сумма длин интервалов, на протяжении которых требования каждого типа находятся в системе. Предлагается метод релаксации директивных сроков. Разрабатывается алгоритм построения оптимального расписания, допустимого относительно релаксированных директивных сроков.
References
1. Танаев, В.С. Теория расписаний. Групповые технологии / В.С. Танаев, М.Я. Koвалев,
2. Я.М. Шафранский. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1998. – 290 с.
3. Potts, C.N. Scheduling with batching: A review / C.N. Potts, M.Y. Kovalyov // European
4. Journal of Operational Research. – 2000. – Vol. 120. – P. 228–249.
5. Баркетов, М.С. Приближенный алгоритм для задачи планирования в цепи производства и поставок / М.С. Баркетов, М.Я. Ковалев // Известия Нац. акад. наук Беларуси. Сер. физ.-мат. наук. – 2006. – № 1. – С. 100–106.
6. Graham, R.L. An efficient algorithm for determining the convex hull of a finite planar set /
7. R.L. Graham // Information Processing Letters. – 1972. – Vol. 1. – P. 132–133.
Review
For citations:
. Informatics. 2010;(2(26)):76-81. (In Russ.)
Views: 480
Email this article 