ІНФОРМАЦІЙНА ТЕХНОЛОГІЯ СКЛАДАННЯ РОЗКЛАДУ НА ОСНОВІ АЛГЕБРИ АДДИТИВНО-ДИЗ’ЮНКТИВНИХ ФОРМ ТА МОДИФІКОВАНОГО МЕТОДУ ПЕРАМНЕНТНОЇ ДЕКОМПОЗИЦІЇ

Анотація

З метою вдосконалення інформаційних технологій складання розкладів занять виникає необхідність у розробці методів, що дозволяють суттєво скоротити кількість комбінаторних об’єктів в процесі роботи алгоритмів генерації матриць розкладів. Наприклад, результатом застосування методу перманентної декомпозиції є сукупність комбінаторних об’єктів – перестановок, комбінацій, розміщень. Для задачі складання розкладів занять в частині формування матриць розкладів метод дає записану в пам’ять сукупність усіх можливих систем різних представників множин, що являють собою стовпчики матриць розкладів (СРПС). Оскільки алгоритм перманентної декомпозиції дає всі можливі СРПС, то це породжує проблему формування остаточного розкладу на основі СРПС чи усіх можливих варіантів розкладів та вимагає розробки спеціальних  алгоритмів. Окремі відомі підходи до розв’язання такої задачі  пов’язані з значною обчислювальною складністю в загальному випадку. Це стосується і підходу на основі відношення порядку на множині матриць розкладу.

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

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