Автоматика и телемеханика, № 7, 2014
Тематический выпуск
МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ
Данный тематический выпуск журнала "Автоматика и телемеханика" посвящен памяти академика Танаева Вячеслава Сергеевича, одного из основоположников теории расписаний в Советском Союзе. Первый подобный выпуск был в № 10 журнала за 2010 г. Данную добрую традицию журнал планирует продолжить и в будущем.
Теория расписаний - это раздел дискретной математики, изучающий математические постановки и методы решения задач оптимального выполнения некоторого набора требований (работ, задач, процессов и т.п.). К теории расписаний относятся вопросы, связанные с построением оптимальных расписаний (календарных планов, графиков) выполнения конечных или периодических комплексов операций в системах, содержащих ограниченные ресурсы. Область приложений результатов теории расписаний включает в себя управление производством, транспортом, строительством, вычислительными системами и др.
Данное направление в науке берет свое начало с работы Генри Гантта [1] в 1903 г., предложившего способ графического отображения расписаний, который сегодня называют диаграммами Гантта. Термин "теория расписаний" предложил известный математик Р. Беллман в 1956 г. [2].
С 50-х гг. 20-го века началось активное теоретическое исследование задач теории расписаний, здесь следует отметить работы Джонсона [3], Джексона [4] и Смита [5], а также монографию Конвея, Максвелла и Миллера [6].
В данном выпуске представлены статьи с результатами исследований по задачам теории расписаний, календарного планирования и смежных областей дискретной оптимизации, подготовленные как учениками В.С. Танаева, так и коллегами, работающими в данной области.
Спектр направлений исследований научной группы под руководством В.С. Танаева был достаточно широк и охватывал основные оптимизационные модели и задачи, возникающие при различной целенаправленной деятельности. В данном выпуске представлены работы, отражающие основные разделы исследований, начало которым в Советском Союзе было положено в трудах В.С. Танаева [7-10].
Представленные статьи относятся к следующим разделам дискретной математики и исследования операций:
• транспортная логистика;
• вычисления на сетях Петри;
• классические задачи на максимин;
• прикладные задачи теории расписаний.
Значительная часть работ из этого выпуска посвящена разработке алгоритмов точного и приближенного решения многоприборных и многостадийных задач теории расписаний.
Результаты и подходы, полученные для задач теории расписаний, зачастую используются при построении эффективных алгоритмов решения практических задач. В данном выпуске представлены работы, посвященные исследованию таких возникающих на практике задач, как задачи планирования производства, формирования портфеля заказов, транспортной логистики и распараллеливания вычислений.
Надеемся, что предлагаемый тематический выпуск будет интересен для широкого круга исследователей в области теории расписаний и смежных разделах математики и техники.
В.С. Танаев скоропостижно скончался в 2002 г. на 63-м году жизни, но заложенными им тематикой и идеологией исследований руководствуются научные коллективы во многих странах мира. Светлая память нашему коллеге и Учителю.
СПИСОК ЛИТЕРАТУРЫ
1. Gantt H.L. Agraphical daily balance in manufacture // ASME Transactions. 1903. V. 24. P. 1322-1336.
2. Bellman R. Mathematical aspects of scheduling theory //J. Soc. Indust. Appl. Math. 1956. V. 4. P. 168-205.
3. Johnson S. V. Optimal two- and three-stage production schedules with setup times included // Naval Res. Logist. Quarterly. 1954. V. 1. P. 61-68.
4. Jackson J.R. Scheduling a production line to minimize maximum tardiness // Management Sci. Res. Project. Res. Report. No. 43. Los Angeles, CA: University of California, 1955.
5. Smith W.E. Various optimizers for single stage production // Naval Res. Logist. Quarterly. 1956. V. 3. P. 59-66.
6. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука. Гл. ред. физ.-мат. лит. 1975. 360 с.
Conway R.W., Maxwell W.L., Miller L.W. Theory of Scheduling. Addison-Wesley, Reading, VA. 1967.
7. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.
8. Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука. Гл. ред. физ.-мат. лит., 1984.
9. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука. Гл. ред. физ.-мат., лит., 1989.
10. Танаев В.С., Ковалёв М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии. Минск: Ин-т техн. кибернетики НАН Белоруси, 1998.
А.А. Лазарев,
Институт проблем управления РАН, Москва
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.