Г. С. Краліна 3О. П. Стьопушкіна icon

Г. С. Краліна 3О. П. Стьопушкіна




Скачати 182.83 Kb.
НазваГ. С. Краліна 3О. П. Стьопушкіна
Дата17.08.2012
Розмір182.83 Kb.
ТипДокументи



В існик НАУ. 2004. №1

УДК 519.8 (045)

1О.Є. Литвиненко, д-р техн. наук

2Г.С. Краліна

3О.П. Стьопушкіна

МАТЕМАТИЧНА МОДЕЛЬ ЗАДАЧІ


СКЛАДАННЯ РОЗКЛАДУ НАВЧАЛЬНИХ ЗАНЯТЬ

Інститут інформатики НАУ, e-mail: 1litvinrnko@nau.edu.ua; 2luan@ukrpost.net; 3styop_1@rbcmail.ru

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

Вступ


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

Два-три десятиліття назад з появою досить продуктивної обчислювальної техніки ця задача викликала бурхливий інтерес розробників автоматизованих систем управління діяльністю вузів [1]. Однак численні спроби цілком автоматизувати її розв’язання не мали успіху. Причиною цього є застосування евристичних алгоритмів, не що потребують побудови яких-небудь математичних моделей. Такий підхід не є перспективним, ос-кільки через подібні алгоритми найчастіше обчислювальний процес вимагає втручання людини (диспетчера, оператора). У крайньому разі розклад занять складається диспетчером вручну, а потім вводиться в комп’ютер для наступного роздрукування.

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

Аналіз досліджень і публікацій


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

У недалекому минулому були початі спроби
формалізації задачі складання розкладу занять [2].

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

Постановка завдання


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

У статті наведено математичну модель задачі складання розкладу занять, що відбиває всі суттєві умови і вимоги, яким повинно відповідати її розв’язання. Модель будується на загальновідомих положеннях.

У навчальному закладі проводяться такі аудиторні заняття: лекції, які читають у потоках (курсах), підпотоках і академічних групах, практичні заняття, які проводять в групах; лабораторні – у підгрупах. Кожна група розбивається на дві підгрупи: “а” і “б” (може бути довільна кількість). Лабораторні заняття підгрупи “б” можуть проводитися паралельно з підгрупою “а”, а також безпосередньо до початку або після завершення аудиторних занять групи в цілому.

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

У математичній моделі задачі складання розк- ладу навчальних занять використовують такі умовні позначення:

– номер групи;

– номер потоку;

– номер підпотоку;

(і) – номер підгрупи “б” і-ї групи;

μ – номер аудиторії або навчальної лабораторії;

– номер пари;

– ідентифікатор викладача;

– потік, до якого належить р-й підпотік;

– потік, до якого належить і-та група;

– підпотік, до якого належить і-та група;

R – множина потоків;

– множина підпотоків;

– множина академічних груп;

– множина викладачів;

– множина аудиторій і спеціалізованих лабораторій навчального закладу;

K – множина номерів пар типового тижня, для якого складається розклад навчальних занять.

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

Для складання розкладу занять необхідно
ввести в комп’ютерну систему такі вхідні дані:

– множина груп, що належить до r-го потоку; ;

– множина груп, що належить до р-го підпотоку; ;

– множина груп, в яких планується проведення практичних занять;

– множина груп, в яких планується проведення лабораторних занять;

– множина викладачів, які читають лекції в r-му потоці; ;

– множина викладачів, які читають лекції в р-му підпотоці; ;

– множина викладачів, які проводять практичні заняття в і-й групі; ;

– множина викладачів, які проводять лабораторні заняття в і-й групі (при введенні вхідних даних у складі множини виділяється підмножина викладачів , яким заплановане проведення лабораторних занять у підгрупі “б”
і-ї групи; ); ;

– множина аудиторій, в яких можуть читатися лекції r-му потокові; ;

– множина аудиторій, в яких можуть читатися лекції р-му підпотокові; ;

– множина аудиторій, у яких можуть проводитися практичні заняття в і-й групі; ;

– множина спеціалізованих навчальних лабораторій, в яких можуть проводитися лабораторні заняття в і-й групі з дисципліни, асоційованої з j-м викладачем; ; ;

– множина днів типового тижня, в яких допускається планувати аудиторні заняття в і-й групі; ;

– множина днів типового тижня, в яких допускається планувати аудиторні заняття j-му викладачеві; ;

, – номера найбільш ранньої і найбільш пізньої пар у d-й день типового тижня, коли j-й викладач може проводити аудиторні заняття; ; ;

τj – максимальна кількість аудиторних занять j-го викладача за один день; ;

– максимальна кількість пар занять і-ї групи за один день; ;

– номер початкової пари для і-ї групи за d-й день типового тижня; ; ;

– множина навчальних дисциплін, з яких j-й викладач читає лекції в r-му потоці; ; ;

– множина навчальних дисциплін, з яких j-й викладач читає лекції в p-му підпотоці; ; ;

– множина навчальних дисциплін, з яких j-й викладач проводить практичні заняття в i-й групі; ; ;

– множина навчальних дисциплін, з яких j-й викладач проводить лабораторні заняття в i-й групі; ; ;

– кількість лекцій з u-ї навчальної
дисципліни, що повинні бути прочитані протягом типового тижня j-м викладачем в r-у потоці; ; ; ;

– кількість лекцій з u-ї навчальної
дисципліни, що повинні бути прочитані протягом типового тижня j-м викладачем в p-у підпотоці; ; ; ;

– кількість практичних занять з u
навчальної дисципліни, що повинні бути проведені протягом типового тижня j-м викладачем в i-й групі; ; ; ;

– кількість лабораторних занять з u-ї навчальної дисципліни, що повинні бути проведені протягом типового тижня j-м викладачем в і-й групі; ; ; ;

νrj – максимальна кількість лекційних занять
j-го викладача в r-му потоці за один день; ; ;

νpj – максимальна кількість лекційних занять j-го викладача в p-му підпотоці за один день; ; ;

ν1ij – максимальна кількість практичних занять j-го викладача в i-й групі за один день; ; ;

ν2ij – максимальна кількість лабораторних занять j-го викладача в i-й групі за один день; ; .

На основі перерахованих (введених ззовні) даних визначають такі множини, необхідні для формалізації розглянутої задачі:

– множина номерів пар за d-й день типового тижня, коли можуть проводитися аудиторні заняття в і-й групі:

; ;

– множина номерів пар за d-й день типового тижня, коли j-й викладач може проводити аудиторні заняття:

; ; ;

– множина номерів пар типового тижня, коли можуть проводитися аудиторні заняття в i-й групі:

; ;

– множина номерів пар типового тижня, коли j-й викладач може проводити аудиторні заняття:

; ;

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

; ;

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

; ;

– повна множина аудиторій і навчальних лабораторій, в яких може проводити заняття j-й викладач:

;

;

де – множина потоків, в яких читає лекції j-й викладач:

;

– множина підпотоків, в яких читає лекції
j-й викладач:

;

– множина груп, в яких j-й викладач проводить практичні заняття:

;

– множина груп, у яких j-й викладач проводить лабораторні заняття:

.

^ Вибір шуканих змінних

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

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

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

; ;

; .

Зміст цих шуканих змінних полягає в наступному. Якщо в результаті розв’язання даної задачі виявляється, що деяка змінна = 1, то -та група на -й парі повинна знаходитися в μ-й аудиторії. При дане твердження неправільне.

Аналогічне змістове навантаження щодо
-го викладача, має змінна .

Розподіл академічних груп на підгрупи під час проведення лабораторних занять вимагає введення додаткових змінних. Символ зіставляється підгрупі “а” і-ї групи, а її підгрупа “б” позначається символом іb (і). Підгрупам “б” надаються номери, що відрізняються від номерів повних груп. Це означає, що якщо – множина номерів підгруп “б”, виділених для проведення лабораторних занять:

,

то .

Тоді розклад лабораторних занять підгруп “б” буде описуватися вектором значень бівалентних змінних:

;

.

Зміст додаткових змінних аналогічний змістові основних змінних .
^

Система обмежень


Математична модель задачі складання розкладу навчальних занять містить такі обмеження:

– обмеження, що забезпечують читання необхідної кількості лекцій у потоках по всіх запланованих навчальних дисциплінах:

, (1)

де – множина номерів пар, на яких j
викладач може читати лекції r-му потокові:

;

– множина номерів пар, на яких можуть читатися лекції r -му потокові:

;

– обмеження, що забезпечують читання необхідної кількості лекцій у підпотоках по всіх запланованих навчальних дисциплінах:



, , (2)

де – множина номерів пар, на яких j
викладач може читати лекції р-у підпотоку:

;

– множина номерів пар, на яких можуть читати лекції р-му підпотоку:

;

– обмеження, що забезпечують проведення необхідної кількості практичних занять по всіх запланованих навчальних дисциплінах:

, (3)

де – множина номерів пар, на яких j-й викладач може проводити практичні заняття в i-й групі:

;

– обмеження, що забезпечують проведення необхідної кількості лабораторних занять по всіх запланованих навчальних дисциплінах для підгруп “а”:

, (4)

для підгруп “б”:

, (5)

де

;

;

;

– обмеження, що забезпечують безперерв-ність занять у групах протягом робочого дня:

, (6)

де







; ;



– обмеження на кількість аудиторних занять викладачів протягом робочого дня:

; ;; (7)

– обмеження на кількість лекцій по кожній дисципліні в потоці протягом одного дня:


; (8)

; ; ,

де – множина номерів пар у d-й день типового тижня, на яких j-й викладач може читати лекції в r-му потоці:

;

– множина днів типового тижня, у які j-й викладач може читати лекції в r-му потоці:

;

– обмеження на кількість лекцій по кожній дисципліні в підпотоці протягом одного дня:

; (9)

; ; ,

де – множина номерів пар в d-й день типового тижня, на яких j-й викладач може читати лекції в p-му підпотоці:

;

– множина днів типового тижня, в які j-й викладач може читати лекції в p-му підпотоці:

;

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

; (10)

; ; ,

де – множина номерів пар в d-й день типового тижня, на яких j-й викладач може проводити практичні (семінарські) заняття в i-й групі:

;

– множина днів типового тижня, в які j
викладач може проводити практичні (семінарські) заняття в i-й групі:

;

– обмеження на кількість лабораторних занять по кожній дисципліні в підгрупі протягом одного дня для підгруп “а”:

; (11)

; ; ;

для підгруп “б”:

(12)

,

де

;

;

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

; ; ; (13)

– обмеження, які виключають можливість появи варіанта розв’язання задачі, що передбачає одночасне перебування в одній аудиторії (лабораторії) двох і більш викладачів:

; ; , (14)

де – множина викладачів, що можуть проводити заняття в -й аудиторії (лабораторії) на k-й парі:

; ;

;

– обмеження, які виключають можливість появи варіанта розв’язання задачі, що передбачає перебування студентської групи одночасно в декількох аудиторіях (лабораторіях):

; ; ; (15)

; ; ; (16)

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

, (17)

де , , – множини потоків, підпотоків і груп, з якими можуть проводитися заняття в -й аудиторії на k-й парі:

; ; ;

; ; ;

; ; ;

– множина груп, що належать до складу студентських формувань, з якими можуть проводитися заняття в -й аудиторії на k-й парі:

; ;

– множина аудиторій, в яких можуть проводитися лекційні і практичні (семінарські) заняття:

,

для лабораторних занять у підгрупах:

, (18)

де – множина спеціалізованих навчальних лабораторій:

;

– множина номерів пар, на яких можуть плануватися лабораторні заняття:

;

– множина підгруп, з якими можуть проводитися лабораторні заняття в -й навчальної лабораторії на k-й парі:

;

– балансові співвідношення, призначені для відтинання абсурдних варіантів розв’язання задачі, для груп:

, (19)

де – сумарна кількість аудиторних занять в
і-й групі протягом типового тижня:



для підгруп “б”:

, (20)

для викладачів:

, (21)

де – сумарна кількість аудиторних занять,
запланованих j-му викладачеві на типовий тиждень:



^ Критерії оптимальності

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

– рівномірність розподілу аудиторних занять у групах по днях типового тижня:

; (22)

– концентрацію аудиторних занять на початку навчального дня:

; (23)

– кількість днів типового тижня, коли сту-дентські групи вільні від аудиторних занять:

; (24)

– кількість днів типового тижня, коли викладачі вільні від аудиторних занять:

; (25)

– кількість “вікон” у викладачів протягом робочого дня:

; (26)

де – максимальна кількість пар аудиторних занять викладачів в один день:

;

σ –кількість “вікон” в аудиторній роботі викладача протягом робочого дня; – множина вик- ладачів, в аудиторній роботі яких можлива наявність :

;

– множина днів типового тижня, коли в
J-го викладача можуть бути :

;

;

.

Висновки

У наведеній формальній постановці задача складання розкладу навчальних занять полягає у відшуканні векторів значень бівалентних змінних

; ; ,

що перетворюють в оптимум (мінімум або максимум) одну з критеріальних функцій (22)–(26) при дотриманні системи обмежень (1)–(21).

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

; (27)

, (28)

де , , – натуральні числа, причому

; – множина номерів незалежних змінних, утворюючих -й добуток;
– незалежні бівалентні змінні: ; – множина номерів добутків незалежних змінних, що належать до критеріальної функції (при ); j-е обмеження (для ); m і n – кількість шуканих змінних і обмежень відповідно.

Для розв’язання задачі (27)–(28) може бути використаний метод спрямованого перебору варіантів, адаптований до задач даного класу [3].
^

Список літератури


1. Самофалов К.Г., Симоненко В.П. Автоматизация составления расписания занятий в вузе. – К.: МВиССО УССР, 1973. – 45 с.

2. Лагоша Б.А., Петропавловская А.В. Комплекс моделей и методов оптимизации расписания занятий в вузе // Экономика и математические методы. – 1993. – Т. 29, вып. 4.

3. Литвиненко А.Е. Метод решения экстремальных комбинаторных задач с нелинейной структурой // Кибернетика. – 1983. – № 5.– С.83–87.

Стаття надійшла до редакції 18.12.03.

А.Е. Литвиненко, А.С. Кралина, Е.П. Степушкина

Математическая модель задачи составления расписания учебных занятий

Приведена математическая модель задачи составления расписания занятий в высшем учебном заведении. Показано, что после тождественных преобразований она сводится к каноническому виду экстремальных комбинаторных задач с нелинейной структурой. Рассмотрен алгоритм решения задачи, реализующий схему направленного перебора вариантов.

O.E. Lytvynenko, G.S. Kralina, E.P. Styopushkina

The mathematical model of the task of compiling the time-table

The mathematical model of the task of compiling the time-table in High-school has been carried out. It has been showed, that the task may be reduced to canonical form of extrimal combinatorial tasks with
unlinear structure after identical transformations. The algorithm of the task’s decision for realizing the scheme of the directed sorting of variants is indicated.



Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи