автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка метода прогнозирования и оценки расписаний в обслуживании систем поточного типа

Введение

Глава 1. Задачи календарного планирования, теории расписаний.

Проблемы и подходы к решению

1.1. Задачи теории расписаний и их классификация

1.2. Проблемы задач теории расписаний

1.3. Методы решения задач теории расписаний

1.4. Постановка задачи диссертационной работы.

Глава 2. Разработка методов и средств прогнозирования решения задач в обслуживании систем поточного типа.

2.1. Аналитическая оценка количества обслуживающих приборов при минимальной длине расписания

2.2. Аналитическая оценка времени выполнения работ при заданных количествах обслуживающих приборов различного типа.

2.3. Аналитическая оценка времени выполнения работ в задачах конвейерного типа

Выводы по главе

Глава 3. Алгоритмизация решения задач в обслуживании систем поточного типа

3.1. Алгоритмы моделирования составления расписаний

3.2. Программное обеспечение

Выводы по главе

Глава 4. Результаты расчетов и статистические испытания моделей составления расписаний.

4.1. Примеры результатов расчетов.

4.2. Статистические испытания моделей составления расписаний.

Выводы по диссертационной работе

В нефтегазовой отрасли применяются различного рода механизмы и машины широкого ассортимента, средства вычислительной техники и коммуникаций, являющиеся продуктами промышленного производства многих отраслей, производств и предприятий, в том числе и собственно нефтегазовой отрасли.

Организация производства и применения этого типа продукции относится к задачам календарного планирования, теории расписаний, обслуживанию систем поточного типа. Так, автоматизация сборочных процессов на базе конвейеризации принята как одно из основных направлений концепции инновационной политики России, являясь приоритетным в технологическом перевооружении общемашиностроительных производств[45].

Это замечание приложимо ко многим странам, в том числе и особо "богатым" нефтью и соответствующими технологиями, производствами, предприятиями по ее добыче, транспорту, хранении переработке. Имеются в виду такие арабские страны Ближнего Востока и Африки как Саудовская Аравия (родина автора данной работы), Ирак, Арабские Эмираты.

Особенно представительно задачи теории расписаний проявляются в вычислительных машинах и системах. Так, в вычислительной технике - это организация в высокопроизводительных машинах в динамике вычислений или/и в аппаратном воплощении конвейеров для сложения или умножения чисел с плавающей точкой, других процедур, организация конвейеров из спецприборов и т. п. Отметим, что конвейеризация вычислений, как и их распараллеливание - это в общем один из немногих магистральных путей роста производительности вычислительных средств. В информационно вычислительных сетях (и в сетях интегрального обслуживания) конвейеризация также имеет место, хотя и менее глобально. Так, конвейер, в общем плане, и есть сама сеть: есть "спецприборы" ввода данных, их обработки, выдачи результатов.

Вместе с тем, несмотря на обилие работ в области теории расписаний, решение задач обслуживания систем поточного типа продолжает оставаться проблематичной в силу их отношения к классу iVF-полных задач (Non Deterministically Polinomial), т.е. не разрешимых за полиномиальное время.

Поэтому предлагаются [42] теоретическое обоснование и реализация такой конвейерной обработки информации, которая существенно шире традиционной. Многомерность конвейерных организаций служит предпосылкой для существенного увеличения достижимой системной производительности конвейера.

Критерием расписания часто является минимальное время обслуживания всего или какого-то множества работ (деталей, задач и т.д.), общее время их выполнения (обработки, решения, и т.д.) или, более строго, длина расписания назначения множества независимых работ, каждая из которых есть цепочка неделимых операций определенной длины (времени), на обслуживающие устройства различного типа (различные приборы, ЭВМ или сети и т.д).

Из-за трудностей математического решения задач теории расписаний[13] возникал интерес, во-первых, к возможности точного решения за счет быстродействия вычислительной техники (полный перебор вариантов плана на электронно-вычислительной машине, иногда в сочетании с эвристическими правилами) и, во-вторых, к приблизительным решениям на базе выборочного метода с применением процедуры Монте-Карло.

На каждом рабочем месте возникает система массового обслуживания с единственным каналом обслуживания в виде прибора с очередью, состоящей из ожидающих обработки изделий, дисциплиной очереди, сформулированной с помощью так называемого "правила приоритетов".

Это правило определяет с помощью особого числа - "индекса приоритетов" - очередности обработки на приборе ожидающих в очереди изделий. Задача возникает не на отдельном рабочем месте, а в цехе, рассматриваемом как сеть очередей, или точнее, как сеть систем массового обслуживания, и состоит задача в том, чтобы выбрать из многочисленных возможных правил приоритетов такое единое для всего цеха правило, которое обеспечивало бы желаемое значение избранного критерия оптимальности расписания (например, среднюю продолжительность производственного цикла, среднюю стоимость незавершенного производства и т. д.).

Для этого попытаемся теоретически обосновать и промоделировать подход к организации конвейерной обработки информации на основе аналитических оценок количества единиц оборудования и времени выполнения работ в задачах конвейерного типа, календарного планирования, теории расписаний. В данной диссертационной работе также рассматриваются наиболее распространенные технологии решения задач календарного планирования, дана их классификация как задач теории расписаний в обслуживании систем поточного типа, сформулированы имеющие здесь место проблемы алгоритмической сложности этих задач, перечислены существующие подходы и методы их решения и предлагается модель для аналитической оценки минимального времени выполнения множества работ с различным оборудованием при ограничении на тип отношения как в "простой задаче с последовательными приборами" [64], когда независимы работы представляют собой цепочки произвольной длины с заданной последовательностью непрерываемых операций.

Также представлено программное обеспечение, алгоритмическая часть которого определяет технологию поддержки принятия решений в задачах календарного планирования.

Выводы по диссертационной работе

В данной диссертационной работе получены следующие результаты:

1. Предложены и разработаны теоретические и методологические основы модели метода аналитических оценок оборудования и времени выполнения работ в задачах теории расписаний конвейерного типа;

2. Разработаны эффективные алгоритмы исследования процесса составления расписания;

3. Разработаны имеющие практическую ценность компьютерные технологии планирования работ по направлениям: а) имитационного моделирования выбора правил назначения работ на выполнение при ограничениях на ресурсы различного типа; б) прогнозной (априорной) оценки минимального срока выполнения множества работ при заданных ресурсах оборудования разного типа (задача анализа); в) оценки количества единиц оборудования различного типа для реализации множества работ в заданные сроки (задача синтеза);

4. Главной особенностью отмеченного интерфейса является снижение сложности данного типа задач, сокращение перебора вариантов расписаний.

5. Разработано и апробировано программное обеспечение по компьютерным технологиям в решении задачи теории расписаний конвейерного типа. Программное обеспечение внедрено в лабораторный практикум учебного процесса по кафедре АСУ РГУ нефти и газа имени И.М. Губкина.

6. Для конкретного производства "SAUDI INDUSTRIAL CENTER" получено по предлагаемой методике расписание примерно на 30% эффективнее существующего, что представляет практическую ценность и предполагаемое внедрение.

1. Абчук В А. Экономико - математические методы: Элементарная математика и логика. Методы исследования операций. - СПБ.: Союз, 1999, с. 320.

2. Аронович А.Б. Экономика и математические методы. М.: Наука, 1970, с. 448-452, 553-556.

3. Антипов В.И. Решение частной задачи календарного планирования методом сравнений, состояний, Сб. "Системы распределения ресурсов на графах".-М.:Вычисл. Центр АН СССР, 1970, с, 7-24.

4. Аронович А.Б. О выборе оптимальных комбинаций локальных правил календарного планирования // Экономика и математические методы. М.: Наука, 6, № 4, 1970, с. 548 - 557.

5. Аронович А.Б. Об одной задаче календарного планирования//Экономика и математические Методы.-М.: Наука, 4, №3, 1968, с. 401-406.

6. БержК. Теория графов и ее применение. М.: ИЛ, 1962, с. 13-24.

7. Бондаренко В.Ф., Кирпичников В.М., Шкляр В.Б. Методы оптимального планирования и диспетчирования вычислительных систем. Обзорная информация. Минск: Бел НИИНТИ, 1976, с. 65-67.

8. Бондаренко A.B. Эвристические подходы к решению задач календарного планирования, Сб. "Автоматизир. системы упр. предприятиями. Тр. семинара", вып. 1, Киев, 1968, с. 47-65.

9. Болун И.Ф. К задаче упорядочения работ в многофазных системах обслуживания // Модели и алгоритмы АСУ. Кишинев, 1986, с. 29-58.

10. Бронштейн И.И., Трахтенгерц Э.А., Шурайц Ю.М. Минимизация времени выполнения набора программ с различной длительностью обработки на многопроцессорной ЦВМ // Автоматика и телемеханика, № 1, 1976, с.179 -186.

11. Бусленко Н.П., Голенко. Д.И., Соболь И.М., Срагович В.Г., трейдер Ю.А. Метод статистических испытаний /метод Монте-Карло/.-м.: ГИФМЛ, 1962, с. 25-32.

12. Бусленко Н.П. Моделирование сложных систем.-М.: Наука, 1978, с. 33-39.

13. Бурдюк В.Я., Шкурба В.В. Теория расписаний. Задачи и методы решений//Кибернетика, Х2 1, 1971, с. 89-102.

14. Бурдюк Т.А. Упорядочение работ для станков равной производительно-стит, Изд. АН СССР, Техническая кибернетика, №1, 1872.

15. Вентцель Е.С., Овчаров JI.A. Задачи и упражнения по теории вероятностей: учеб. Пособие для вузов. М.: Высшая школа, 2000, с. 27-30.

16. Виленкин С.Я., Трахтенгерц Э.А. Математическое обеспечение управляющих вычислительных машин. — М.: Энергия, 1972, с. 29-32.

17. Власюк Б.А. Задача об оптимальном расписании обработки деталей на трех последовательных, Изв. АН СССР, Техническая кибернетика, №4, 1967.

18. Гэрн М., Джонсон Д.Р. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, с. 30-37.

19. Глебов Н.И., Перепелица В.А. О нижней и верхней оценках для одной задачи теории расписаний, Сб."Исслед. go кибернетике",- М.: Наука 1970, с. 11-17.

20. Гордон B.C., Шафранский Я.М. К вопросу минимизации функций на множестве перестановок частично упорядоченных элементов.- Изв. АН БССР. Сер. Физ.-матем. наук, №2, 1979, с. 122-124.

21. Гордон B.C., Танаев B.C. О минимальных задачах теории расписаний с одним прибором//Изв. АН БССР. Сер.физ.матем. Наука, 1982, №3, с. 3-9.

22. Даниелян Э.А. Приоритетные задачи в системах обслуживания одним прибором, Статистика и стохастические системы, вып. 13, Изд-во МГУ, 1971.

23. Данильченко A.M., Панишев A.B. О частных случаях задачи трех станков//Изв. АН ССР. Техн. Кибернетика, №4, 1986, с. 197.

24. Духовный И.М. Системы обслуживания с обобщенными приоритетами и ненадежным прибором, Изв. АН СССР, Техническая кибернетика, №1, 1970, с. 34-42.

25. Джонсон Д.Р. Очереди с динамическим правилом приоритета. Сб. "Календарное планирование". М.: Наука, 1966, с. 357 - 377.

26. Зак Ю.А. Алгоритмы решения задач "я коммивояжеров" // Кибернетика, №1, 1972, с. 99-106.

27. Канцедал С.А. Вычислительные алгоритмы решения задач теории расписаний,-Изв. АН СССР, Техническая кибернетика, 1982, №3, с. 42-48.

28. Канцедал С.А. Алгоритм сокращения поиска решении в задаче теории расписаний сетевой структуры // Автомат, и телемех, 1982., №4, с. 72-77.

29. Кершенбаум В.Я., Петухов Ю.С., Щарафиев Р.Г. Машиностроительный комплекс России: состояние, проблемы, тенденции развития // Надежность и сертификация оборудования для нефти и газа №3, 2000, с. 35-40.

30. Климов Г.П. Некоторые решенные и нерешенные задачи в обслуживании последовательной цепочкой приборов, Изв. АН СССР, техническая кибернетика, №6, 1970, с. 42-45.

31. Клейнен Д.Ж. Статистические методы в имитационном моделировании. Вып. 1, 2.-М: Статистика, 1978, с. 30-33.

32. Командровский В.Г. Планирование работ в ИВС. Конвейеризация вычислений-М.: РГУ нефти и газа, 1997, с. 22.

33. Командровский В.Г. Теория вычислительных систем. 4.1. -М.: МИНХ и ГП, 1977, с. 66.

34. Командровский В.Г. Сборник задач и упражнений по теории вычислительных систем. Ч.2.-М.:МИНГ, 1987, с. 77.

35. Командровский В.Г. Выбор однородных ресурсов и оценка времени реализации работ в ИВС: методическое руководство к лабораторной работе.-М.: ГАНГ, 1997, с. 12.

36. Командровский В.Г., Торгов Ю.И. Два этапа оптимизации синтеза вычислительных систем. Сб.: Проектирование и применение иерархических мультипроцессорных систем. - М.: ВЦ АН СССР, 1984, 33 с.

37. Командровский В.Г. Выбор ресурсов в однородной вычислительной системе по нижней оценке количества процессоров. М.: МИНХ и ГП, 1986,43 с.

38. Командровский В.Г., Сирдах М.Д. Автоматизация технологий решения конвейерной задачи. Метод, пособие к лаб. работе по курсу. М.: РГУ нефти и газа, 2000, - 28 с.

39. Командровский В.Г. Сирдах М.Д. О технологиях решения конвейерной задачи. Тезисы докладов 4-й конференции "Актуальные проблемы состояния и развития нефтегазового комплекса России".-М.: РГУ нефти и газа, 25-26янв. 2001, секция 6, с. 23.

40. Коффман Э.Г. Теория расписаний и вычислительные машины М.: Наука, 1984,333 с.

41. Конвей Р.В., Максвелл В.JI. Календарное планирование в условиях сети очередей с дисциплиной по кратчайщей операции, Сб. "Календарное планирование"-М.: Наука 1975, с. 321-347.

42. Конвей Р.В., Максвелл В.Л., Миллер JI.B. Теория расписаний. Главная редакция физико-математической литературы изд-ва (Наука), 1975, с. 359.

43. Кузьмин И.В., Березюк Н.Т., Фурманов К.К. Синтез вычислительных алгоритмов управлений и контроля. К.: Техника, 1975, с. 58-64.

44. Лагоша Б.А. Методы имитационного моделирования: Учебное пособие. Моск. экономико статистический ин-т, 1986, с. 23-32.

45. Лагоша Б.А. Экономика организационные основы отраслевого управления.-М.: Наука 1981, с. 33-42.

46. Лавинский Г.В, Петренко П.А., Семенов Н.П. Проблемы оценки сложности алгоритмов и вычислений при проектировании управляющих систем.-Киев, Управляющие системы и машины, 1977, №2, с. 6-13.

47. Латыпов И.Ш. О сложности одной задачи теории расписаний // Системы програмного обеспечения решения задач оптимального направления: Тез. Докл. IX Всесоюзн. Симпозиума.-М.: 1986, с. 88-89.

48. Лепешинский H.A. О классификации 2Х п задач Джонсона Беллмана, Изв. АН БССР, сер. Физ.-мат. наук, № 1,1967, с. 18-21.

49. Липский B.C., Корнев М.Д. Составление оптимальных расписаний для параллельно действующих процессоров, Изв. АН СССР, Техническая кибернетика, №3, 1972, с. 45-48.

50. Лыткин И.П. Об одной задаче календарного планирования // Экономика и матем. методы 7, № 2, 1977, с. 286-289.

51. Михалевич B.C., Шкурба В.В. Последовательные схемы оптимизации в задачах упорядочения выполнения работ. Кибернетика, № 2, 1966, с. 34-40.

52. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных задачах оптимального распределения ресурсов-М.: Наука, 1983, с. 87-92.

53. МутД. Томпсон Д. Календарное планирование,"Прогресс", 1966, с. 30-35.

54. Однаш Й. Алгоритмы распределения ресурсов неоднородной многопроцессорной системы.- В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. М.: Наука, 1982, с. 320-324.

55. Подчасова Т.П., Португал В.М. и др. Эвристические методы календарного планирования Киев: Техника, 1980, с. 30-35.

56. Розанов Ю.А. Случайные процессы.-М.: Наука, 1971. с. 20-23.

57. Сирдах М.Д. К алгоритмизации процесса решения конвейерной задачи. НТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности.-М.: ВНИИОЭНГ, 2000. -№ 2, с. 7-11.

58. Сирдах М.Д. Диалоговая система информационного обеспечения технологий решения задач конвейерного типа//НТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности. -М.: ВНИИОЭНГ, 2002. №3-4.

59. Солодовников В.В., Бирюков В.Ф., Тумаркин В.И. Принцип сложности в теории управления. -М.: Наука, 1977.

60. Советов Б.Я., Яковлев С.А. Моделирование систем.-М.: Высшая школа, 1986, с. 23-27.

61. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. -М.: Наука, 1975, с. 12-26.

62. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы.-М.: Наука, 1983, с. 77-79.

63. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы.-М.: Наука. Гл. ред. физ.-мат. лит, 1989, 328 с.

64. Фишер Г., Томпсон Г.Л. Комбинации локальных правил календарного планирования применительно к самонастраивающимся на вероятностной основе программ для ЭВМ. Сб. "Календарное планирование". М.: Прогресс, 1966, с. 260-275.

65. Цвиркун А.Д., Акинфиев В.К., Фильппов В.А. Имитационное моделирование в задачах синтеза структуры сложных систем.-М.: Наука, 1985.

66. Халафян A.A. Разномаршрутная задача теории расписаний // Ученые науке и народному хозяйству. Краснодару 1983, с. 276-280.

67. Шахбазян К.В., Тушкина Т.А., Сохранская B.C. Статистические испытания различных методов диспетчеризации для многопроцессорных систем.- Программирование, 1976, №4, с. 91-100.

68. Шахбазян К.В., Лебединская М.Б. Эффективные методы автоматизации составления расписания для одной машины (обзор), Записки научных семинаров ЛОМИ АН СССР, 111, 1981, с. 195-217.

69. Шевченко В.Н. Задача составления оптиманьного расписания на п станках. Сб. "Пробл. кибернетики", вып. 18, 1967, с. 129-146.

70. Шкурба В.В. Задача трех станков.-М.: 1976, с. 45-55.

71. Шкурба В.В., Селивончик В.К. Расписания, имитационное моделирование и оптиматизация/'/'Кибернетика, № 1, 1981, с. 91—96.