Одноетапні задачі теорії розкладів у багаторівневій системі планування

dc.contributor.authorМельник, Олена Олексіївна
dc.date.accessioned2013-07-08T11:53:24Z
dc.date.available2013-07-08T11:53:24Z
dc.date.issued2013
dc.description.abstractРобота присвячена розробленню нових методів вирішення задач теорії розкладів за критерієм мінімізації сумарного випередження і запізнення з урахуванням налагодження приладів в багаторівневій системі планування з мережевим представленням технологічних процесів та обмеженими ресурсами. Вперше показано взаємозв’язок між методами розв’язання задач мінімізації сумарного запізнення завдань відносно директивних строків (МСЗ), мінімізації сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом (МВЗ), мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями (1-МВЗН), що дало змогу на основі методів розв’язання задач МСЗ та МВЗ побудувати нові ефективні евристичні методи розв’язання задачі 1-МВЗН, які, на відміну від існуючих, дають можливість одержати розв’язок задач великої розмірності. Розроблені та статистично обґрунтовані нові ефективні методи для розв’язання задач мінімізації сумарного випередження і запізнення при виконанні груп завдань одним приладом з налагодженнями та мінімізації сумарного випередження і запізнення при виконанні завдань одним приладом з налагодженнями, залежними від послідовності. Створено систему моделювання для статистичного дослідження ефективності розроблених методів. Досліджено, що запропоновані методи дали змогу отримати високоякісні наближені розв’язки з невеликими часовими витрат. Удосконалено програмне забезпечення системи за рахунок включення до її складу задачі 1-МВЗН та методів її розв’язання. Це дало змогу підвищити ефективність системи, розширити її функції та коло прикладних задач її застосовування. Розроблено інформаційні технології та реалізовано у вигляді алгоритмів методи розв’язання досліджуваних задач у багаторівневій системі планування з мережевим представленням технологічних процесів та обмеженими ресурсами. Работа посвящена разработке методов и информационных технологий решения задач теории расписаний по критерию минимизации суммарного опережения и запаздывания с учетом наладок приборов в системе иерархического планирования с сетевым представлением технологических процессов и ограниченными ресурсами. Производства с сетевым представлением технологических процессов и ограниченными ресурсами охватывают около 80% всех видов производственных систем. Эффективность процесса планирования с учетом технологий производства существенно зависит от наличия переналадок оборудования. В некоторых случаях время наладки прибора может быть более длительным по сравнению со временем выполнения прибором работы. В результате анализа иерархической модели планирования и управления в сложных производственных системах, учитывающих сетевое представление технологических процессов и ограниченные ресурсы, предложенной Згуровским Н.З. и Павловым А.А., показано, что ее модификация за счет включения в состав математического обеспечения моделей задач планирования, учитывающих время наладки приборов, даст возможность максимизировать прибыль предприятий, уменьшить себестоимость продукции и обеспечить более рациональное применение оборудования. На основе методов решения задач минимизации суммарного запаздывания заданий относительно директивных сроков (МСЗ), минимизации суммарного опережения и запаздывания относительно директивных сроков при выполнении независимых заданий одним прибором (МОЗ) разработаны четыре новых метода решения задач минимизации суммарного опережения и запаздывания при выполнении групп заданий одним прибором с наладками (1-МОЗН). Методы решения задач минимизации суммарного опережения и запаздывания при выполнении групп заданий одним прибором с наладками реализованы в виде алгоритмов: А1 – для случаев, когда простои оборудования разрешены, А2 − при запрещенных простоях оборудования, А3 и А4 – для наладок, зависимых от последовательности заданий. Создана система моделирования для статистического исследования эффективности разработанных методов. Результаты исследований показали, что разработанные эвристические методы позволили получить близкие к оптимальным решения задач большой размерности (от 50 до 500 заданий), для которых точные методы не применимы. Установлено, что разработанные эвристические методы обеспечивают получение решений оптимизационных задач з учетом наладок приборов с высоким качеством за значительно меньшее время сравнительно с методом ветвей и границ (в 17–407.5 раз для исследованных задач размерностью 10-25 заданий, для которых возможно применение точного метода; среднее отклонение значения функционала от оптимального находится в пределах 1-8.3%). Эффективность алгоритмов А3, А4 качественно зависит от определения окрестности текущих решений. Алгоритм А3, основанный на разработанной эвристике, дает решение за меньшее в 23.8 раз среднее время по сравнению с алгоритмом А4. Алгоритм А4, который основан на разработанной эвристике и известном методе локального поиска, позволяет получить более точные результаты, так как рассматривает более широкую окрестность текущих решений (среднее отклонение значения функционала от оптимального для алгоритму А4 составляет около 2%, для А3 − около 8,3%). Все предложенные методы и алгоритмы имеют самостоятельное значение, а также являются основой для создания эвристик для применения в более сложных моделях. Например, практические задачи для нескольких приборов раскладываются на подзадачи для одного прибора, которые решаются отдельно, что существенно упрощает решение многоприборных задач. Разработанные методы и модели могут широко применяться в многоуровневых производственных системах различного назначения. Модифицировано программное обеспечение системы за счет включения в ее состав задачи 1-МОЗН и методов ее решения. Это позволило расширить функции системы, повысить ее эффективность, а также расширить прикладную область ее применения. Разработаны информационные технологии и реализованы алгоритмы решения исследуемых задач в многоуровневой системе планирования объектов с сетевым представлением технологических процессов и ограниченными ресурсами. This thesis is a complex research devoted to the developing of new methods for solving scheduling theory on the criterion of minimizing the total earliness and tardiness in the system with a network representation of processes and limited resources. For the first time the relationship between methods of solving problems of minimizing the total tardiness of the tasks concerning the directive terms, minimizing the total earliness and tardiness directive terms in solving the independent tasks with one device adjustment, minimizing the total earliness and tardiness of the tasks with one device adjustment. The author statistically confirmed and developed new efficient methods for solving the problems of minimizing the total earliness and tardiness in the process of doing the group tasks with one device adjustment and the problems of minimizing the total earliness and tardiness of the tasks with one device adjustment depending on the sequence. A system of modeling for statistical study of the effectiveness of the developed methods is created. Software system is modified by means of incorporating into its structure the problem of minimizing the total earliness and tardiness of the tasks with one device adjustment and methods of its solution. This allows us to expand the functions of the system and increase its efficiency. The information technologies are developed and algorithms are implemented as methods of the studied problems in a multi-level system planning facilities with a network representation of technological processes and limited resources.uk_UA
dc.identifier.citationМельник О. О. Одноетапні задачі теорії розкладів у багаторівневій системі планування : автореферат дисертації на здобуття наукового ступеня кандидата технічних наук : 05.13.06 - інформаційні технології / Олена Олексіївна Мельник ; Національний університет "Львівська політехніка". - Львів, 2013. - 26 с.uk_UA
dc.identifier.urihttps://ena.lpnu.ua/handle/ntb/20239
dc.language.isouauk_UA
dc.publisherНаціональний університет "Львівська політехніка"uk_UA
dc.subjectінформаційні технологіїuk_UA
dc.subjectтеорія розкладівuk_UA
dc.subjectодноетапні задачіuk_UA
dc.subjectсистеми плануванняuk_UA
dc.subjectналагодження обладнанняuk_UA
dc.subjectкритерій мінімізації сумарного випередження і запізненняuk_UA
dc.subjectинформационные технологииuk_UA
dc.subjectтеория расписанийuk_UA
dc.subjectодноэтапные задачиuk_UA
dc.subjectсистемы планированияuk_UA
dc.subjectналадка оборудованияuk_UA
dc.subjectкритерий минимизации суммарного опережения и запаздыванияuk_UA
dc.subjectinformation technologiesuk_UA
dc.subjectscheduling theoryuk_UA
dc.subjectone-stage problemuk_UA
dc.subjectplanning systemsuk_UA
dc.subjectdevice adjustmentuk_UA
dc.subjectcriteria of minimizing of the total earliness-tardinessuk_UA
dc.titleОдноетапні задачі теорії розкладів у багаторівневій системі плануванняuk_UA
dc.title.alternativeОдноэтапные задачи теории расписаний в многоуровневой системе планированияuk_UA
dc.title.alternativeOne-stage task scheduling theory in a multi-level system planninguk_UA
dc.typeAutoreferatuk_UA

Files

Original bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
avt_01342682.doc
Size:
1.29 MB
Format:
Microsoft Word

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.06 KB
Format:
Item-specific license agreed upon to submission
Description: