Анотація до роботи:

1. Базилевич Р. П. Штучна ієрархічна кластеризація в задачах розміщення різногабаритних елементів / Р. П. Базилевич, І. Ф. Щерб’юк // Штучний інтелект. – 2002. - № 3. - С. 484-489.

2. Базилевич Р. П. ППП "Розмел" для формування розміщення різногабаритних елементів. / Р. П. Базилевич, І. Ф. Щерб’юк // Вісник Національного університету "Львівська політехніка": Комп’ютерні науки та інформаційні технології. - 2005. - № 543. - С. 64-67.

3. Базилевич Р. П. Низхідне розміщення різногабаритних елементів з оптимізацією методом сканувальної області / Р. П. Базилевич, І. Ф. Щерб’юк // Вісник Національного університету "Львівська політехніка": Комп’ютерна інженерія та інформаційні технології. - 2002. - № 468. - С. - 34-37.

4. Базилевич Р. П. Застосування ієрархічної кластеризації для розміщення різногабаритних елементів / Р. П. Базилевич, І. Ф. Щерб’юк // Вісник Національного університету "Львівська політехніка": Комп’ютерна інженерія та інформаційні технології. - 2002. - № 450. - С. 80-84.

5. Базилевич Р. П. Низхідне багаторівневе розміщення різногабаритних елементів / Р. П. Базилевич, І. Ф. Щерб’юк // Комп’ютерні технології друкарства: алгоритми, сигнали, системи. - 2002. - № 9. - С. 90-95.

6. Базилевич Р. П. Розміщення різногабаритних елементів поєднанням ієрархічних висхідної та низхідної стратегій / Р. П. Базилевич, І. Ф. Щерб’юк // Вісник Національного університету "Львівська політехніка": Комп’ютерна інженерія та інформаційні технології. - 2003.- № 496. - С. 5-10.

7. Базилевич Р. П. Початкове розміщення елементів методом групування та дворівневого макромоделювання / Р. П. Базилевич, І. Ф. Щерб’юк // Вісник Національного університету "Львівська політехніка": Комп’ютерна інженерія та інформаційні технології. - 2001. - № 433. - С. 48-50.

8. Базилевич Р. П. Оптимізація розміщення елементів методом точкового сканування / Р. П. Базилевич, І. Ф. Щерб’юк // Комп’ютерні технології друкарства: алгоритми, сигнали, системи. - 2000. - № 4. - С. 179-182.

9. Базилевич Р. П. Початкове розміщення елементів нарощуванням / Р. П. Базилевич, І. Ф. Щерб’юк // Вісник Національного університету "Львівська політехніка": Комп’ютерна інженерія та інформаційні технології. - 2000. - № 392. - С. 54-57.

10. Базилевич Р.П. Оптимізація орієнтації елементів в задачах розміщення / Р. П. Базилевич, І. Ф. Щерб’юк // Вісник Національного університету "Львівська політехніка": Комп’ютерні науки та інформаційні технології. - 2007. № 604. - С. 47- 51.

11. Базилевич Р. П. Алгоритмические и программные средства для размещения разногабаритных элементов на конструктиве / Р. П. Базилевич, И. Ф. Щербюк // Автоматизация проектирования дискретных систем (НАН Республики Беларусь). - Минск, Беларусь, 2007. - № 6. - С. 157-164.

12. Базилевич Р. П. Оптимізація розміщення елементів з візуалізацією дерева згортання / Р. П. Базилевич, І. Ф. Щерб’юк // Proceedings of the International conference on computer science and information technologies. - Lviv, 2007. - P. 144-146.

АНОТАЦІЇ

Щерб’юк І.Ф. Алгоритмічне та програмне забезпечення для розміщення різногабаритних елементів електронних пристроїв комбінованими методами ієрархічної оптимізації. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12 – "Системи автоматизації проектувальних робіт". – Національний університет "Львівська політехніка", Львів, 2008.

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

Досліджено особливості задач розміщення для різногабаритних елементів. Розроблено алгоритм багаторівневого низхідного ієрархічного розміщення з можливістю оптимізації на кожному рівні декомпозиції сканувальною областю для макромоделей. Розроблено алгоритм на основі дворівневого групування за висхідною стратегією. Розвинуто алгоритм сканувальної області з врахуванням особливостей реалізації для різногабаритних елементів. Вперше реалізовано алгоритм сканувальної області для макромоделей. Розроблено алгоритм точкового сканування елементом та групою елементів конструктиву.

Проведено експериментальні дослідження розроблених алгоритмів та дано порівняльний аналіз ефективності кожного з них. Для розробленого алгоритмічного забезпечення створено комп’ютерну систему для використання в проектуванні електронних пристроїв, зокрема друкованих плат.

В результаті виконаних досліджень розв’язано наукову задачу розроблення методів та алгоритмів розміщення різногабаритних елементів електронних пристроїв, які поєднують принципи багаторівневої декомпозиції та ієрархічної оптимізації і реалізовані в комп’ютерній системі "Розмел" з інтеграцією в сучасній системі автоматизованого проектування P-CAD, що покращило якість проектування.

Отримано такі наукові і практичні результати:

1. Аналіз та дослідження відомих систем автоматизованого проектування засобів приладобудівної та електронної техніки (зокрема, P-CAD та ACCEL) виявили, що якість розв’язування задачі розміщення різногабаритних елементів електронних пристроїв є недостатньо високою та вимагає покращення.

2. Для покращення якості розміщення різногабаритних елементів конструкцій електронної апаратури в системах автоматизованого проектування запропоновано поєднати багаторівневі алгоритми низхідного та висхідного розміщення базових та макроелементів з алгоритмами глобальної та локальної оптимізації на кожному рівні ієрархічної декомпозиції схеми.

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

• висхідного дворівневого розміщення з послідовним нарощенням елементів, придатного для отримання якісних розв’язків з невеликою кількістю елементів;

  низхідного ієрархічного багаторівневого розміщення з використанням макромоделей, придатного для отримання якісних розв’язків для задач з великою кількістю елементів.

  Обґрунтовано доцільність сумісного використання обох підходів: на верхніх рівнях – низхідне ієрархічне розміщення, на нижніх двох рівнях – послідовне нарощування елементів з врахуванням зв’язків з рештою елементів.

  4. Для оптимізації положення як базових, так і макроелементів, розроблено, розвинуто та експериментально досліджено алгоритми:

  – точкового сканування (розроблено вперше);

  – сканувальної області.

  Обґрунтовано доцільність сумісного комбінування обох алгоритмів на кожному кроці ієрархічної декомпозиції схеми.

  5. Розроблені та досліджені алгоритмічні засоби мають близьку до лінійної обчислювальну складність та ряд додаткових нових функційних можливостей, зокрема виділяти сильнозв’язані групи елементів з наступним описом їх ієрархічно-вкладеними макромоделями, комбіновано поєднувати на кожному кроці багаторівневої декомпозиції набір алгоритмів початкового розміщення та його оптимізації з використанням макромоделювання. Алгоритмічні засоби забезпечують також вибір орієнтації елементів, виділення фіксованих місць для окремих елементів, виділення зон, заборонених для розміщення елементів.

  Експериментально досліджено ефективність розроблених алгоритмів та програмних засобів на задачах реальних конструкцій електронної апаратури. Застосування розробленої комп’ютерної системи "Розмел" для таких задач підвищило якість отриманих розв’язків до 26,6% в порівнянні з результатами, одержаними системою P-CAD.

  6. Розроблено комп’ютерну систему "Розмел", яка реалізує комплекс розроблених алгоритмічних засобів, має гнучку модульну структуру з власними засобами керування та призначена як для автономного використання, так і для взаємодії з системами автоматизованого проектування широкого використання, такими як P-CAD, ACCEL та іншими.

  Система має засоби інтерактивної взаємодії, які забезпечують покращення якості отриманих розв’язків для задач, що погано формалізуються, особливо у випадку великого розкиду габаритів елементів, наявності фіксованих елементів та заборонених зон. Вперше запропоновано виводити в діалогове вікно (для використання проектантом) інформацію про структуру дерева оптимального згортання, що дозволяє оперувати ієрархічно-вкладеними макроелементами, які відповідають групам сильнозв’язаних елементів – кластерам схеми.

  7. Розроблену комп’ютерну систему "Розмел" впроваджено в процес реального проектування друкованих плат в Науково-дослідному і конструкторському інституті електронної вимірювальної та обчислювальної техніки (м.Львів) та в навчальний процес на кафедрі "Програмне забезпечення" Національного університету „Львівська політехніка”.