Свойства оптимальных расписаний и эффективные алгоритмы решения некоторых NP — трудных задач теории расписаний для одного прибора
Диссертация
Интерпретация задач теории расписаний в терминах смешанных графов проведена в работах Л. П. Матюшкова и В. С. Танаева, Е. Ба-лаша, Б. Сассмана. Применению матричных методов к решению этих вопросов посвящена работа. Цикл работ по минимизации линейных форм на различных подмножествах множества перестановок проведен Д. А. Супруненко, В. С. Айзенштатом, Н. А. Лепешинским, И. М. Кунцевичем, Д. Н… Читать ещё >
Содержание
- 1. Свойства оптимальных расписаний задачи минимизации максимального временного смещения
- 1. 1. — Постановка задачи
- 1. 2. Свойства оптимальных расписаний общего случая задачи
- 1. 3. Свойства оптимальных расписаний частных случаев задачи 1| r3Lmaz
- 2. Эффективные алгоритмы решения задачи минимизации максимального временного смещения
- 2. 1. Процедура построения приближенного расписания для задачи 1|r.
djLmax. Оценка абсолютной погрешности - 2. 2. Процедура построения допустимого расписания для задачи 1
djLmax - 2. 3. Алгоритм решения задачи 1|гг
djLmax - 2. 4. Полиномиальные алгоритмы решения частных случаев задачи 1|г.-
djLmax - 2. 5. Приближенный алгоритм решения общего случая задачи. Оценка абсолютной погрешности
- 2. 1. Процедура построения приближенного расписания для задачи 1|r.
Список литературы
- Беркута О. Н., Лазарев А. А. Алгоритм сложности 0(п3) решения задачи минимизации суммарного запаздывания// Иссл. по прикл. мат.- Выпуск 22.- Казань, 1995.- С. 67 78.
- Бурдюк В. Я., Шкурба В. В. Теория расписаний. Задачи и методы решений// Кибернетика 1971- N 1- С. 89 — 102.
- Бурков В. Н., Ловецкий С. Е. Методы решения экстремальных комбинаторных задач (обзор)// Изв. АН СССР, Техн. кибернетика.-1968.- N 4.- С. 82 93.
- Бурков В. Н., Ловецкий С. Е. Методы решения экстремальных задач комбинаторного типа (обзор)// Автоматика и телемеханика.-1968.- N 11.- С. 68 93.
- Визит В. Г. О расписаниях, соблюдающих директивные сроки выполнения работ// Кибернетика.- 1981- N 1.- С. 128 135.
- Визит В. Г., Клипкер И. А. Полиномиальный алгоритм решения задачи Гэри Джонсона о составлении расписания// Сообщ. АН Груз. ССР.- 1981, — N 1.- С. 29 — 32.
- Власюк Б. А. Задача оптимального расписания при наличии переналадок// Экономика и матем. методы, — 1967 N 3 — С. 79 — 84.
- Гик Е. Я., Левнер Е. В. Решение некоторых задач календарного планирования для одного станка// В кн.: Вопросы матем. теории управл. систем и ее применнен. в металлургии.- 1974.- С. 22 25.
- Голунков Ю. В. О сложности представления подстановок симметрической полугруппы через элементы систем образующих// Журн. Кибернетика.- 1971.- N 1- С. 43 44.
- Голунков Ю. В. Программно-автоматная реализация подстановок симметрической полугруппы. Часть 1// Журн. Кибернетика.-1971.- N 5.- С. 5 12.
- Голунков Ю. В. Программно-автоматная реализация подстановок симметрической полугруппы. Часть 2// Журн. Кибернетика.-1975.- N 5.- С. 35 42.
- Гордон В. С. Об оптимальных расписаниях с прерываниями процесса обслуживания// Изв. АН БССР. Сер. физ.- матем. н.- 1974.-N 5.- С. 129 130.
- Гордон В. С. Детерминированная система обслуживания с минимаксным критерием оптимальности и частично упорядоченным множеством требований// Автоматиз. техн. подготовки пр-ва.-1977.- N 4.- С. 70 75.
- Гордон В. С. Детерминированные одностадийные системы обслуживания с прерываниями// В кн.: Вычислит, техн. в машиностроении.- Минск.- 1973.- С. 30 38.
- Гордон В. С. Допустимые относительно директивных сроков расписания с наименьшим суммарным штрафом// Труды 8-го Болг.
- Польск. симпозиума «Оптимизация, принятие решений, микропроцессорные системы», 17 21 октября 1983 г.- София.- С. 153 — 156.
- Гордон В. С., Танаев В. С. О минимаксных задачах теории расписаний с одним прибором// Изв. АН БССР. Сер. физ.- матем-1983.- N 3.- С. 3 9.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ.- М.: Мир, 1982 416 е., ил.
- Диниц Е. А., Кронрод М. А. Один алгоритм решения задачи о назначении// ДАН СССР 189.- 1969.- N 1, — С. 23 25.
- Зиндер Я. А. Об алгоритмах решения некоторых задач упорядочения/ / В кн.: Алгоритмы и программы Горький, 1977.- вып 1.- С. 114 — 123.
- Карп Р. М. Сводимость комбинаторных проблем// В кн.: Кибер-нет. сб.- М.: Мир, 1975.- Вып. 12.- С. 16 38.
- Китик М. Г. К вопросу «сужения» ветвления в задаче одного станка// Кибернетика, — 1972.- N 1.- С. 145 147.
- Кнут Д. Искусство программирования для ЭВМ. т. 3: Сортировка и поиск, — М.: Мир, — 1973.- 348 с.
- Ковалев М. Я. Интервальные е приближенные алгоритмы решения дискретных экстремальных задач: Дис. канд. физ.-мат. наук-Минск, 1986, 110 с.
- Копылов Г. Н. Точное решение задачи одного станка// Весн. Яро-славск. ун-та, 1975, — Вып. 9 С. 52 — 60.
- Лазарев А. А. Эффективные алгоритмы решения некоторых задач теории расписаний для одного прибора с директивными сроками обслуживания требований: Дис. канд. физ.-мат. наук.- Казань, 1989, 108 с.
- Лазарев А. А. Исследование задач теории расписаний с помощью преобразований// Иссл. по прикл. мат.- Вып. 12.- Казань, 1984-С. 63 74.
- Лазарев А. А. Алгоритм решения задачи минимизации максимального временного смещения для одного прибора// Иссл. операций и оптимальное упр.- Деп в ВИНИТИ N 3795 85ДЕП — С. 21 — 30.
- Лазарев А. А., Шульгина О. Н. К решению задачи планирования производственно-экономической деятельности предприятия// Иссл. по прикл. мат.- Выпуск 21.- Казань, 1999.- С. 155 169.
- Лазарев А. А., Шульгина О. Н. Полиномиально разрешимые частные случаи задачи минимизации максимального временного смещения/ / Ред. Журн. «Изв. Вузов. Математика».- Казан, ун-т.- Казань, 2000.- 11 е.- Библ. 8 назв.- Деп в ВИНИТИ 28.11.00, N 3019-В00.
- Лебединская Н. Б. Минимизация максимального отклонения в случае прерывания работ// Зап. науч. семинаров. Ленингр. отд. Матем. ин-та АН СССР, 1978.- С. 117 124.
- Лебединская Н. Б. Минимизация максимального штрафа в случае прерывания работ// Зап. науч. семинаров. Ленингр. отд. Матем. ин-та АН СССР, 1980.- С. 61 67.
- Левин Г. М., Танаев В. С. Об одном классе комбинаторных задач оптимизации// Изв. АН БССР, сер. физ.- мат. наук.- 1968.- С 30 -35.
- Леонтьев В. К. Построение на заданном множестве точек гамиль-тонова цикла, близкого по длине к найкратчайшему// Сб. «Акту-альн. вопр. техн. кибернетики».- М: «Наука».- 1972.- С. 244 248.
- Лобановский Н. М. Об оптимальном планировании последовательности выполнения работ на одной или двух машинах// Сб «Кибернетика и управление».- М.: Наука, 1967.- С. 85 92.
- Матюшков Л. П., Танаев В. С. Программные генераторы допустимых расписаний// Сб. «Вычислительная техника в машиностроении».- Минск, 1967.- С. 35 48.
- Прокофьев О. Н. Выбор оптимальной очередности обслуживания// Изв. АН СССР, Техн. кибернетика, — 1972, — С. 104 107.
- Сотсков Ю. Н. Оптимальное расписание множества работ заданное смешанным графом// Изв. АН БССР. Сер. физ.- мат. наук.-1977.- N 47, — С. 133.
- Супруненко Д. А., Айзенштат В. С., Лепешинский Н. А. Экстремальные значения функций на множествах перестановок// Тезисы докл. 1 Всес. конф. по исслед. операций.- Минск, 1972.- С. 61 64.
- Танаев В. С. Некоторые оптимизируемые функции одностадийного производства// ДАН БССР 9.- 1965.- N 1.- С. 11 14.
- Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы.-М.: Наука, Гл. ред. физ.-мат. лит., 1989.- 328 с.
- Танаев В. С., Левин Г. М. Об оптимальном поведении систем с частично ограниченной памятью// Изв. АН БССР, сер. физ.- мат. наук.- 1967.- N 3.- С. 82 88.
- Тузиков А. В. Об одном классе векторной оптимизации на перестановках/ / В кн.: Алгоритмы и программы решения экстремальных задач и смежные вопросы, — Минск, 1982.- С. 62 70.
- Тузиков А. В. О двухкритериальных задачах теории расписаний/ / Оптимизация, принятие решений, микропроцессорные системы. Труды 8-й Болг, — Польск. симпозиума, 17 21 окт. 1983 г. София, — С. 163 — 168.
- Шульгина О. Н. Исследование задачи минимизации максимального временного смещения для одного прибора// Казан, ун-т.- Казань, 2000.- 21 е.- Библ. 3 назв.- Деп в ВИНИТИ 28.06.00, N 1809-В00.
- Шульгина О. Н. Построение допустимого расписания относительно заданной оценки значения целевой функции// Материалы международной конференции «Дискретный анализ и исследование операций», 26 июня 1 июля — Новосибирск, 2000 — С. 179.
- Шульгина О. Н. Алгоритм решения частного случая задачи минимизации максимального временного смещения// Тез. докл. Всероссийской науч. конф. «Алгоритмический анализ неустойчивых задач».- Екатеринбург, 26 февраля 2 марта 2001 года.- С. 316.
- Ashour S, Hiremath S. R. A branch-and-bound approach to the job-shop scheduling problem// Int. J. Prod. Res 1973 — V. 11, N 1- P. 47 — 58.
- Baker K. R., Lawler E. L., Lenstra J. K., Rinnoy Kan A. N. G. Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints// Oper. Res.-1983.- n 2.- P. 381 386.
- В alas E. Mashine Scheduling via Disjunctive Graphs: An Implicit Enumeration Algorithm// Oper. Res.- 1969, — V. 17, N 6.- P. 941 -957.
- Bowman E. N. The Schedule Sequencing Problem// Oper. Res. 7.1959.- N 5.
- Bratley P., Florian M., Robillard, P. On sequencing with earliest starts and due dates with application to computing bounds for the (nmGFmux) problem// Nav. Res. Log. Quart.- 1973.- V. 20.- P. 57 67.
- Brooks G. N. and White C. R. An Algorithm for Finding Optimal or Near Optimal Solutions to the Production Scheduling Problem// J. Ind. Eng. 16.- 1965.-V 16, N 1.- P. 34 — 40.
- Brucker P., Lenstra J. K., Rinnoy Kan A. N. G. Complexity of machine scheduling problems// Math. Cent. Afd. Math. Beslisk. Amsterdam.- 1975.- BW 43.- 29 pp.
- Burstall R. M. A heuristic method for a jobscheduling problem// Oper. Res. Quart. 17.- 1966.- N 3 P. 291 — 304.
- Buzacott J. A., Dutta S. K. Sequencing many jobs on a multipurpose facility// Nav. Res. Log. Quart. 18.- 1971.- N 1- P. 75 82.
- Charlton J. M., Death С. C. A method of solution for general machine scheduling problems// Oper. Res.- 1970.- V. 18, N 4.- P. 689 707.
- Carlier J. The one machine sequencing problem// Eur. J. Oper. Res.-1982, — V. 11, N 1, — P. 42 — 47.
- Dessouky M. I., Margenthaler C. R. The one machine sequencing problem with early starts and dates// AIIE Trans 4.- 1972 — N 3.- P. 214 — 222.
- Du J., Leung J. Y-T. Minimizing total tardiness on one machine is NP-hard// Math. Oper. Res. 15, — 1990.- P. 483 495.
- Fisher M. L. Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part 1// Oper. Res.- 1973, — V. 21, N 5.- P. 1114 1127.
- Fisher M. L. A dual algorithm for the one machine scheduling problem// Mathem. Program.- 1976.- N 11- P. 229 — 251.
- Elmagraby S. E. The one machine sequencing problem with delay costs// J. Industr. Engng 19.- 1968 N 2.- P. 105 — 108.
- Florian M., Trepart P., McMahon G. An implicit enumeration algorithm for the machine sequencing problem// Manag. Sci.(B).-1971.- V. 17, N 12.- P. 782 792.
- Frederickson G. N. Sheduling unit-time tasks with integer release times and deadlines// Inform. Process. Lett. 16.- 1983.- P. 171 173.
- Garey M. R., Jonson D. S., Simons В. В., Tarjan R. E. Scheduling unite time tasks with arbitrary release times and deadline// SI AM J. Comput.- 1981.- V. 10, N 2.- P.256 — 269.
- Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: a survey// Ann. Discrete Math 1979 — N 5 — P. 287 -326.
- GigUo R. J. and Wagner H. M. Approximate Solutions to the Three -Machine Scheduling Problem// Oper. Res. 12, — 1964, — N 2.
- Held M., Karp R. M. A dynamic programming approach to sequencing problem// J. Soc. Industr. and Appl. Math. 10.- 1962.- N 1.- P. 196 210.
- Horn W. A. Some simple scheduling algorithms// Nav. Res. Log. Quart. 21 1974, — N 1.- P. 177 — 185.
- Jackson J. R. Scheduling a production line to minimize maximum tardiness// Res. Report 43, Manag. Sci. Res Project, USLA, Jan, 1955.
- Kovalev M. Y. One one machine scheduling to minimize the namber of late items and the total tardiness// Minsk, 1991.(Preprint// Institute of Enginering Cybernetics of the BSSR Academy of Sciences, N4)
- Lageweg B. JLenstra J. K., Rinnooy Kan A. H. G. Minimizing maximum lateness on one machine: computational experience and some applications// Statist, neer.- 1976.- N 1- P. 25 41.
- Lageweg B. J., Lenstra J. K., Rinnooy Kan A. H. G. Job shop scheduling by implicit enumeration// Manag. Sci.- 1977.- V. 24, N 4.- P. 441 — 450.
- Lakshminarayan S., Lakshmanan R., Papineau R. L, Rochette R. Optimal single machine scheduling with earliness and tardiness penalties// Oper. Res.- 1978.- V. 26, N 6.- P. 1079 — 1082.
- Lawler E. R. On scheduling problems with deferral costs// Manag. Sci.- 1964.- V. 11, N 2.- P. 280 288.
- Lawler E. R. Optimal sequencing of a single machine subject to precedence constraints// Manag. Sci.- 1973.- V. 19, N 5.- P. 544 -546.
- Lawler E. R. A «pseudopolynomial» algorithm for sequencing jobs to minimize total tardiness// Ann. Discrete Math.- 1977.- N 1.- P. 331 342.
- Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Sequencing and Schedulinq: Algorithms and Complexity// Elsevier Science Publishers В. V.- 1993, — V. 4, — P. 445 520.
- Lawler E. R., Moore J. M. A functional eguation and its application to resource allocation and sequencing problems// Manag. Sci.- 1969.-V. 16, N 1.- P. 77 84.
- Lazarev A., Schul’gina 0. Problem minimizing maximum lateness for single machine: properties, procedures, algorithms// 9-th Belgian-French-German Conference on Optimization, Namur, September 7−11.-Namur, 1998.- P. 45.
- Lenstra J. K., Rinnooy Kan A. H. G., Bruker P. Complexity of machine scheduling problems// Ann. Descrete Math.- 1977.- N 1.-P. 343 362.
- Manne A. S. On the Job Shop Scheduling Problem// Oper. Res.-1960.- V. 8, N 2.
- McMahon G. В., Florian M. On sequencing with ready times and due dates to minimize maximum lateness// Oper. Res.- 1975.- V. 23.- P. 475 482.
- Monma C. L. Sequencing to minimize the maximum job cost// Oper. Res.- 1980.- V. 28, N 4, — P. 942 951.
- Nabeshima I. Unified treatment on single machine schedulig problems// Repts. Univ. Electro Communs.-1971.- V. 22, N 2.- P. 29 — 38.
- Nabeshima I. General scheduling algorithms with applications to parallel scheduling and multiprogramming scheduling// J. Oper. Res. Soc. Japan.- 1971.- V. 14, N 2, — P. 72 99.
- Nugent С. E. On Sampling Approaches to the Solution of the n by- m Static Sequencing Problem// Ph. D. thesis, Cornell University. -1964.
- Okamura K., Yamashina H. Eastablishment of linear sequences// Mem. Fas. Engng. Kyorto Univ. 31.- 1969.- N 3.- P. 307 331.
- Schindler S. Sheduling general monitor systems// In Proc. 9-th Haw. Int. Conf. Syst. Sci. Honolulu.- 1976.- P. 122 124.
- SchuVgina Oksana N. Construction of feasible schedule with designated evaluation of criterion function// French- German- Italian Conference on Optimization, Montpellier, September 04−08−2000.- P. 61.
- SchuVgina Oksana Pseudopolynomial algoritm for the problem of minimizing maximum lateness// Scan2000, Karlsruhe, September 19- 22, 2000.
- Shwimer J. On the n-job, one-machine, sequence-indepent scheduling problem with tardiness penalties. A branch-bound solution// Manag. Sci.- 1979.- V. 18, N 6.- P. 301 313.
- Sidney J. B. Optimal singlemachine scheduling with earlines and tardiness penalties// Oper. Res.- 1977, — V. 25, N 1.- P. 62 — 69.
- Simons B. A. A fast algorithm for single processor scheduling// In: 19th Annu. Symp. Found. Comput. Sci., Ann. Arbor, Mich.- New York, 1978.- P. 246 252.
- Smith W. E. Various optimizers for single stage production// Nav. Res. Log. Quart.- 1956.- V. 3, N 1.- P. 59 66.
- Story A. E. and Wagner H. M. Computational Experience with Integer Programming for Job Shop Scheduling// Industrial Scheduling, J. E.103
- Muth and G. L. Thompson eds. Englewood Cliffs, N. J., Prentice -Hall.- 1963.- Ch. 14.
- Sussmann B. Scheduling problems with interval disjunctions// Z. Operat. Res. Ser. A16.- 1972.- N 5.- P. 165 178.
- Wagner H. M. An Integer Linear Programming Model for Machine Scheduling// Nav. Res. Log. Quart.- 1959.- V. 6, N 2.