Свойства оптимальных расписаний и эффективные алгоритмы решения некоторых NP - трудных задач теории расписаний для одного прибора

• Автор: Шульгина, Оксана Николаевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Казань
• Количество страниц: 103 с.

Содержание
Введение
1 Свойства оптимальных расписаний задачи минимизации максимального временного смещения

1.1 ■ Постановка задачи

1.2 Свойства оптимальных расписаний общего случая задачи

1|С'1 Ьтах

1.3 Свойства оптимальных расписаний частных случаев задачи 1г^тах

2 Эффективные алгоритмы решения задачи минимизации максимального временного смещения

2.1 Процедура построения приближенного расписания для за-

дачи 1 т.[ < г^> с1^Ь1пах. Оценка абсолютной погрешности

2.2 Процедура построения допустимого расписания для задачи 1|г; < гj? (3,1 > Ф,-Ь1пах
2.3 Алгоритм решения задачи 1|г.; < г?, с!, > <1^Ьпшх
2.4 Полиномиальные алгоритмы решения частных случаев
задачи 1|г., < > й^Ьтах
2.5 Приближенный алгоритм решения общего случая задачи.
Оценка абсолютной погрешности
3 Задача минимизации суммарного запаздывания
3.1 Постановка задачи и некоторые ее свойства
3.2 Свойства оптимальных расписаний частного случая задачи
3.3 Полиномиальный алгоритм решения частного случая задачи
Заключение
Список литературы

Введение
Задачи упорядочения носят самый общий характер. Они возникают повсюду, где существует возможность выбора очередности выполнения работ. Изучаемые в теории расписаний модели возникают при календарном планировании производства, транспортных перевозок, военных операций, обучения, информационно-вычислительных процессов и при других видах целенаправленной деятельности. На практике болынист-во задач так или иначе решается. Однако эти решения принимаются интуитивно, так как принятие наилучшего решения связано с большими временными затратами. Поэтому вопросы построения эффективных по времени алгоритмов составления наилучших расписаний остаются актуальными.
Первые публикации по решению задач теории расписаний появились в начале 1950 - х годов [73], [98]. Следует отметить, что уже на начальной стадии развития теории расписаний стало ясно, что задачи оптимального упорядочения трудоемки. Для их решения привлекались известные результаты прикладной математики, а также разрабатывались новые подходы и методы. Значительная часть результатов в области теории расписаний касается выявления сложности проблемы. Вопросы сложности задач теории расписаний рассматривались, например, в работах [17], [20], [56], [62].

построения оптимального расписания на множестве трудо-
емкости О (гг2 + пх) операций, где 0(х) - трудоемкость процедуры отыскания И*.
Доказательство. Пусть существует процедура отыскания подмножества IV* для любого множества IV' С N. Пусть в схеме 1.1 к > 1. Поскольку ^ то согласно лемме 1.4 существует оптимальное расписание тг* е П(Л^,П) такое, что Д}' -н> {_? £ Ик : > г ^}
и, кроме того, Следовательно, Ык ^ Щ+1. Тогда из лем-
мы 1.7 следует сугцествание оптимального расписания гг £ П(А^,П) такого, что тг = (тг*,тг2*), где тг* € Пг(ЛГй,^), тг2* 6 П(ДГ*+1,Т(тск,^)). Поэтому, на рассматриваемой итерации схемы будет построено начало {КгтЗа) оптимального расписания на множестве П(1У/,, £/.), и задача построения оптимального расписания на этом множестве сводится к задаче построения оптимального расписания на П(Лг^.+1,Т(7?^,^)), которое на следующей итерации схемы будет строится аналогично 7г. Следовательно, на некотором т - м шаге схемы 1.1 таком, что т < п и 1 = 0, будет построено оптимальное расписание
*■»,. = 7 го) е п(аг , 1).
Оценим трудоемкость схемы 1.1. Пусть О(х) - трудоемкость отыскания Лг*. Количество итераций схемы 1.1, очевидно, не превосходит п. Оценим трудоемкость одной итерации. Если перенумеровать требования по неубыванию моментов поступления, то для отыскания N^+1 и 7Г/. потребуется 0(п) операций. Для нахождения Nk и П-+1 также необходимо 0(п) операций. И, наконец, трудоемкость построения Аг* составляет О(х) операций. Следовательно, для выполнения одной итерации схемы потребуется 0(п + а:) операций. Поскольку количество итераций не превышает п и для перенумерации требований необходимо 0(п к^п)