Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

Разработка метода прогнозирования и оценки расписаний в обслуживании систем поточного типа

Диссертация: Разработка метода прогнозирования и оценки расписаний в обслуживании систем поточного типа
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Глава 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. И.В., Березюк Н. Т., Фурманов К. К. Синтез вычислительных алгоритмов управлений и контроля. К.: Техника, 1975, с. 58−64.
  43. .А. Методы имитационного моделирования: Учебное пособие. Моск. экономико статистический ин-т, 1986, с. 23−32.
  44. .А. Экономика организационные основы отраслевого управления.-М.: Наука 1981, с. 33−42.
  45. Лавинский Г. В, Петренко П. А., Семенов Н. П. Проблемы оценки сложности алгоритмов и вычислений при проектировании управляющих систем.-Киев, Управляющие системы и машины, 1977, № 2, с. 6−13.
  46. И.Ш. О сложности одной задачи теории расписаний // Системы програмного обеспечения решения задач оптимального направления: Тез. Докл. IX Всесоюзн. Симпозиума.-М.: 1986, с. 88−89.
  47. H.A. О классификации 2Х п задач Джонсона Беллмана, Изв. АН БССР, сер. Физ.-мат. наук, № 1,1967, с. 18−21.
  48. B.C., Корнев М. Д. Составление оптимальных расписаний для параллельно действующих процессоров, Изв. АН СССР, Техническая кибернетика, № 3, 1972, с. 45−48.
  49. И.П. Об одной задаче календарного планирования // Экономика и матем. методы 7, № 2, 1977, с. 286−289.
  50. B.C., Шкурба В. В. Последовательные схемы оптимизации в задачах упорядочения выполнения работ. Кибернетика, № 2, 1966, с. 34−40.
  51. B.C., Кукса А. И. Методы последовательной оптимизации в дискретных задачах оптимального распределения ресурсов-М.: Наука, 1983, с. 87−92.
  52. МутД. Томпсон Д. Календарное планирование,"Прогресс», 1966, с. 30−35.
  53. Й. Алгоритмы распределения ресурсов неоднородной многопроцессорной системы.- В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. М.: Наука, 1982, с. 320−324.
  54. Т.П., Португал В. М. и др. Эвристические методы календарного планирования Киев: Техника, 1980, с. 30−35.
  55. Ю.А. Случайные процессы.-М.: Наука, 1971. с. 20−23.
  56. М.Д. К алгоритмизации процесса решения конвейерной задачи. НТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности.-М.: ВНИИОЭНГ, 2000. -№ 2, с. 7−11.
  57. М.Д. Диалоговая система информационного обеспечения технологий решения задач конвейерного типа//НТЖ. Автоматизация, телемеханизация и связь в нефтяной промышленности. -М.: ВНИИОЭНГ, 2002. № 3−4.
  58. В.В., Бирюков В. Ф., Тумаркин В. И. Принцип сложности в теории управления. -М.: Наука, 1977.
  59. .Я., Яковлев С. А. Моделирование систем.-М.: Высшая школа, 1986, с. 23−27.
  60. B.C., Шкурба В. В. Введение в теорию расписаний. -М.: Наука, 1975, с. 12−26.
  61. B.C., Гордон B.C., Шафранский Я. М. Теория расписаний. Одностадийные системы.-М.: Наука, 1983, с. 77−79.
  62. B.C., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы.-М.: Наука. Гл. ред. физ.-мат. лит, 1989, 328 с.
  63. Г., Томпсон Г. Л. Комбинации локальных правил календарного планирования применительно к самонастраивающимся на вероятностной основе программ для ЭВМ. Сб. «Календарное планирование». М.: Прогресс, 1966, с. 260−275.
  64. А.Д., Акинфиев В. К., Фильппов В. А. Имитационное моделирование в задачах синтеза структуры сложных систем.-М.: Наука, 1985.
  65. A.A. Разномаршрутная задача теории расписаний // Ученые науке и народному хозяйству. Краснодару 1983, с. 276−280.
  66. К.В., Тушкина Т. А., Сохранская B.C. Статистические испытания различных методов диспетчеризации для многопроцессорных систем.- Программирование, 1976, № 4, с. 91−100.
  67. К.В., Лебединская М. Б. Эффективные методы автоматизации составления расписания для одной машины (обзор), Записки научных семинаров ЛОМИ АН СССР, 111, 1981, с. 195−217.
  68. В.Н. Задача составления оптиманьного расписания на п станках. Сб. «Пробл. кибернетики», вып. 18, 1967, с. 129−146.
  69. В.В. Задача трех станков.-М.: 1976, с. 45−55.
  70. В.В., Селивончик В. К. Расписания, имитационное моделирование и оптиматизация/'/'Кибернетика, № 1, 1981, с. 91—96.
Заполнить форму текущей работой

На отлично!