ІНФОРМАЦІЙНА ТЕХНОЛОГІЯ ГЕНЕРАЦІЇ МАТРИЦЬ РОЗКЛАДІВ ЗГІДНО ПЕРМАНЕНТНОЇ ДЕКОМПОЗИЦІЇ

Анотація

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

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

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

Проведені експерименти та розрахунки обчислювальної складності підтверджують ефективність методу перманентної декомпозиції.