Одноетапні задачі теорії розкладів у багаторівневій системі планування
Електронний науковий архів Науково-технічної бібліотеки Національного університету "Львівська політехніка"
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Одноетапні задачі теорії розкладів у багаторівневій системі планування
Одноэтапные задачи теории расписаний в многоуровневой системе планирования One-stage task scheduling theory in a multi-level system planning |
|
| Creator |
Мельник, Олена Олексіївна
|
|
| Subject |
інформаційні технології
теорія розкладів одноетапні задачі системи планування налагодження обладнання критерій мінімізації сумарного випередження і запізнення информационные технологии теория расписаний одноэтапные задачи системы планирования наладка оборудования критерий минимизации суммарного опережения и запаздывания information technologies scheduling theory one-stage problem planning systems device adjustment criteria of minimizing of the total earliness-tardiness |
|
| Description |
Робота присвячена розробленню нових методів вирішення задач теорії розкладів за критерієм мінімізації сумарного випередження і запізнення з урахуванням налагодження приладів в багаторівневій системі планування з мережевим представленням технологічних процесів та обмеженими ресурсами. Вперше показано взаємозв’язок між методами розв’язання задач мінімізації сумарного запізнення завдань відносно директивних строків (МСЗ), мінімізації сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом (МВЗ), мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями (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. |
|
| Date |
2013-07-08T11:53:24Z
2013-07-08T11:53:24Z 2013 |
|
| Type |
Autoreferat
|
|
| Identifier |
Мельник О. О. Одноетапні задачі теорії розкладів у багаторівневій системі планування : автореферат дисертації на здобуття наукового ступеня кандидата технічних наук : 05.13.06 - інформаційні технології / Олена Олексіївна Мельник ; Національний університет "Львівська політехніка". - Львів, 2013. - 26 с.
http://ena.lp.edu.ua:8080/handle/ntb/20239 |
|
| Language |
ua
|
|
| Publisher |
Національний університет "Львівська політехніка"
|
|