Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Вступ актуальність теми дослідження

Вступ актуальність теми дослідження




Сторінка4/9
Дата конвертації10.03.2017
Розмір1.31 Mb.
1   2   3   4   5   6   7   8   9

У силу об'єктивних причин система складання розкладу у вузі (мається на увазі великий державний вуз) обов'язково повинна реалізовувати ряд основних функцій:

- врахування побажань викладачів;

- закріплення обов'язкових аудиторій;

- вказівка ​​бажаних аудиторій;

- облік переходу між корпусами;

- об'єднання груп в потоки по будь-якої сукупності дисциплін;

- розбиття на підгрупи;

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

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

Зробимо більш детальний огляд декількох продуктів.

Програма-аналог MySchool. В середині навчальної екосистеми MySchool передбачене Автоматичне складання розкладу школи. Достатньо внести всі дані (або імпортувати з інших програм).

Екосисте́ма - це сукупність живих організмів, які пристосувалися до спільного проживання в певному середовищі існування, утворюючи з ним єдине ціле.
Імпорт - ввезення товарів, послуг (іноді може вживатися щодо капіталу, знань, технологій)
Наразі реалізована підтримка експорту/імпорту даних.

Якщо ви вже маєте складений розклад у паперовому або електронному варінті. Якщо у вас є картинки розклад уроків вам залишилось заповнити його в системі буквально у кілька кліків.

Як ви бачите складання розкладу уроків є легким. Можна використати шаблони розкладу уроків. В разі виявлення накладок система повідомить про це.

Розклад занять це один з основних документів, які створюються в останні дні літніх канікул і за ним школа буде жити весь рік.

Докуме́нт - базова теоретична конструкція, яка відноситься до всього, що може бути збережене або представлене, щоб служити як доказ для певної мети.
Тому вимоги до розкладу уроків стоять високі.

Ручне складання розкладу уроків потребує тримати в пам'яті багато параметрів. На початку навчального року багато сторонніх питань – зосередитись можна тільки у вечері чи на вихідні, часті термінові зміни розкладу на початку (вересень) вимагають швидкої переробки розкладу.

Автоматичне складання розкладу уроків не потребує тримати в пам'яті багато параметрів їх достатньо наперед зібрати перед складанням розкладу. Висока швидкість складання дозволяє паралельно вирішувати багато завдань.

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

Чорновий варіант розкладу готовий за кілька хвилин і школа готова сісти за парти.

На рисунку 1.5 зображенно вікно інтерфейсу програми MySchool.


Рисунок 1.5 – інтерфейс програми MySchool


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

При введенні даних враховується:

режим роботи кожного вчителя;

режим роботи кожного класу;

можливіть зменшення вікон у вчителів;

вимоги до методичних днів для вчителів (якщо дозволяє тижневе навантаження);

вимога проводити уроки в певному визначеному кабінеті;

важкість уроків в балах для дотримання санітарних норм при складанні розкладу;

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

В багатій оселі могло бути два(або більше) кабінети - для господаря і господині. Жіночий кабінет також використовувався як вітальня і будуар.

ділення класів на групи (до 6 груп);

зведення декількох класів на один урок;

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

введення вимоги для «мигалки», або навантаження 0,5 год. на тиждень.

Та інше…


Складання розкладу відбувається у різних режимах.

Автоматичному. Для шкіл з невеликою кількістю класі. Невеликим числом сумісників та за відсутності важких ділень на групи.

Напівавтоматичному. Для шкіл з важким діленням на групи, браком кабінетів та великою кількістю сумісників.

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

При складанні шкільного розкладу за допомогою програми Ректор 3 можна не відступати від звичних методик ручного способу.

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

В програмі легко реалізувати поетапне складання розкладу, автоматичну та ручну корекцію розкладу одного класу чи паралелі, одного вчителя чи декількох.

Програма здійснює перевіркускладеного шкільного розкладу, згідно вимог, які введені корисувачем.

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

При усуненні проблеми програма «пропустить» розклад як готовий.

Створений розклад програма передає у відомі формати:

Word, для редагування зовнішнього вигляду розкладу перед виведенням на друк;

Excel – для більш зручного редагування, у тому числі і підготовки до друку у великому форматі;

HTML – формат для публікації розкладу в мережі інтернет на сторінці школи.

Інтерне́т (від англ. Internet), міжмере́жжя - всесвітня система взаємосполучених комп'ютерних мереж, що базуються на комплекті Інтернет-протоколів. Інтернет також називають мережею мереж. Інтернет складається з мільйонів локальних і глобальних приватних, публічних, академічних, ділових і урядових мереж, пов'язаних між собою з використанням різноманітних дротових, оптичних і бездротових технологій.

Програма складання шкільного розкладу Ректор 3 дозволяє роздрукувати розклад:

- всієї школи;

- окремої паралелі чи декількох класів;

- окремого класу;

- всіх вчителів;

- деяких вчителів (наприклад, кафедри);

- одного вчителя.

Розглянемо програму-аналог Методист. Перш ніж розпочинати складати розклад занять, необхідно підготувати такі допоміжні матеріали, як:

- робочий навчальний план;

- навчальні програми з предметів робочого навчального плану;

- інформація про мережу аудиторій;

- інформація про наявність навчальних кабінетів і про закріплення їх за викладачами;

- розподіл педагогічного навантаження викладачів;

- розподіл кураторських годин;

- інформація про розподіл аудиторій на підгрупи при вивченні окремих навчальних предметів;

- список керівників методичних об’єднань;

- інформація про викладачів, які є сумісниками;

- інформація про методичні дні адміністрації, голови профспілкового комітету;

Адміністрáція - це: «державна адміністрація» у значенні певних органів державного управління. Розрізняють - А. центральну (Президент, Кабінет Міністрів, інші центральні відомства) та місцеву (решта органів державного управління); із запровадженням інституту президентства створено апарат при Президентові України, який має назву «Адміністрація Президента України».
Професі́йна спі́лка (профспі́лка) - добровільна неприбуткова громадська організація, галузева спілка, що об'єднує громадян, пов'язаних спільними інтересами за родом їх професійної (трудової) діяльності (навчання).

- розклад дзвінків;

- особисті побажання викладачів щодо розкладу уроків;

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

- форми довідкових таблиць для складання розкладу.

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

- Прізвище, ім’я, по батькові.

- Предмет, який викладач викладає.

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

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

Аудиторії, в яких викладач викладає навчальні предмети.

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

Номер аудиторії, закріпленого за викладачем.

Кількість годин на тиждень по аудиторіях.

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

У примітках можна зазначити такі дані про кожного викладача:

- методичний день;

- дні (години) роботи сумісників;

- особисті побажання до розкладу.

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

Допоміжна таблиця складається з двох стовпчиків:

- розподіл заняття по аудиторіях протягом тижня;

Сто́впчик - видовжена середня циліндрична частина маточки. Зазвичай на стовпчику височіє приймочка.

- стовпчик «Резерв», що призначений для коригування розкладу заняття.

Заповнювати допоміжну таблицю доцільно у такій послідовності:

Розставити пари викладачів-сумісників та адміністрації, а також викладачів, чиї заняття з різних причин зафіксовані за днями тижня або за годинами дня.

Розставити пари які на один день в одній і тій самій аудиторії можна ставити лише один з цих предметів.

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

Фізи́чна культу́ра, фізкультура - складова частина культури, пов'язана з системою фізичного виховання, організації спорту, спеціальних наукових дослідів, технічних засобів, потрібних для фізичного виховання і спорту, суспільної та особистої гігієни, раціональної організації активного відпочинку тощо.
Це дає змогу раціональніше використовувати навчальні аудиторії у ВНЗ.

Розставити уроки викладачів-«предметників»: спочатку тих, які мають здвоєні уроки, а потім решти викладачів -«предметників».

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

На наступному необхідно переконатися у правильності розстановки занять.

Перевірити відповідність розкладу робочому навчальному плану.

Підрахувати кількість занять у групах.

У допоміжній таблиці слід підрахувати:

по вертикалі в кожному стовпчику — щоденну кількість занять у групі;

по горизонталі для кожного класу — кількість занять з предмета на тиждень.

Горизонталь, ізогіпса (англ. contour lines, horizontal, isohyps, нім. Höhenkurve f, Horizontale f; рос. горизонталь, изогипса; від дав.-гр. ισος - равний і дав.-гр. ὕψος - висота) - лінія на плані (карті), яка з'єднує точки земної поверхні з однаковою абсолютною висотою.

Підрахувати навантаження кожного викладача.

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

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

1. Розставити занятя паралелі 1-х курсів протягом усього робочого тижня, потім 2-х і так далі до паралелі 6-х курсів. За потреби під час розстановки занять наступних паралелей можна вносити зміни в розстановку занять уже заповненого розкладу.

При складанні розкладу занять необхідно враховувати, те, що біоритмічний оптимум розумової працездатності припадає на 10-12 години. У цей час відзначається найбільша ефективність засвоєння матеріалу за найменших психофізіологічних витрат організму. Тому в розкладі занять більш складні предмети потрібно ставити на цей час.

2. У розкладі на кожен день відкоригувати «вікна» між уроками викладачів-«предметників» та зайнятість навчальних аудиторій, зручніше й раціональніше розмістити занятя протягом дня тощо.

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

На цьому отримуємо робочий варіант розкладу уроків.

Для остаточної перевірки розкладу необхідно:

підрахувати по горизонталі тижневе навантаження кожного викладача, а по вертикалі — переконатися, що у розкладі кожної групи немає «вікон»;

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

усунути зайві «вікна» в викладачів-«предметників»;

раціональніше розмістити «складні» заняття;

з’ясувати наявність методичних днів для викладачів;

З наведеного списку мабуть тільки програма "Методист" більш-менш відповідає необхідної функціональності програмного продукту складання розкладу у вузі. Такий стан речей легко пояснюється тим, що шкільна освіта на сьогоднішній день більш "стандартизована" (в сенсі організації навчального процесу), ніж вузівська. Така стандартизація веде до великого обсягу потенційного ринку продажів програмного забезпечення та окупності розробки шляхом продажу великої кількості копій продукту за порівняно низькою ціною.

Стандартиза́ція - діяльність, що полягає в установленні положень для загального та неодноразового використання щодо наявних чи потенційних завдань і спрямована на досягнення оптимального ступеня впорядкованості в певній сфері.

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

Задача теорії розкладів у загальній її постановці вважається досить привабливою, хоча досягнення навіть невеликого прогресу на шляху до вирішення пов'язано, як правило, з величезними труднощами. Незважаючи на те, що завданнями теорії розкладів займалися багато вельми кваліфіковані фахівці, досі нікому не вдалося отримати яких-небудь істотних результатів. Безуспішні спроби отримання таких результатів, як правило, не публікуються і це частково обумовлює той факт, що завдання продовжує привертати увагу багатьох дослідників уявною простотою постановки [17].

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

При́стрій (англ. device, appliance, нім. Vorrichtung f, Einrichtung f) - обладнання, конструктивно завершена технічна система, що має певне функціональне призначення і за допомогою якої виконується яка-небудь робота або спрощується, полегшується певний процес.
Детерміні́зм (лат. determinatus - «визначений», «обмежений») - філософське матеріалістичне вчення про загальну об’єктивну зумовленість явищ природи, суспільства та людської психіки, зокрема волі, внаслідок причинності, тобто такого зв’язку явищ, за якого одне явище (причина) за певних умов породжує інше (дію).

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

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

- всі процесори (тобто у випадку навчального розкладу - аудиторії) мають місткість - деяке число C ≥ 1. Місткість процесора визначає кількість завдань, які він може одночасно "обробляти" в даний момент часу (у відношенні непоодинокими процесорами було б цікавим розглянути варіант, коли в якості процесора виступає не аудиторія, а викладач, а як завдання потік з однієї або більше навчальних груп, з якими він працює);

- в якості безлічі завдань для розподілу виступають навчальні заняття викладача з навчальними групами;

- модель часу в системі є дискретною; весь розподіл передбачається періодично повторюваним протягом деякого тимчасового інтервалу;

- всі завдання виконуються за однаковий час, який приймається за одиницю дискретизації тимчасового інтервалу;

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

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

-У підсумку, формулювання задачі складання розкладу навчальних занять звучить наступним чином: "Для заданого набору навчальних аудиторій (в даному випадку під навчальною аудиторією розуміється широке коло приміщень, в яких проводяться навчальні заняття (від комп'ютерної аудиторії до спортивного залу)) і заданого набору часових інтервалів (тобто по суті, уроків або навчальних пар) побудувати такий розподіл навчальних занять для всіх об'єктів (вчителі та навчальні групи), для якого обраний критерій оптимальності є найкращим " [18].

Примі́щення - частина внутрішнього об'єму будівлі, обмежена будівельними елементами, з можливістю входу і виходу.

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

- розклад складається з розрахунку не більше двох пар в день;

- всі пари проводяться в одному корпусі;

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

- подальша декомпозиція моделі не проводиться;

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

- всі коефіцієнти моделі і шукані змінні цілочисельні;

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

2 МАТЕМАТИЧНА МОДЕЛЬ ПРОЦЕСУ ФОРМУВАННЯ РОЗКЛАДУ
2.1 Математична модель об‘єктів розкладу
Складання розкладу для процесу обслуговування означає, що для кожної операції на часовій осі задається підмножина, на якій ця операція виконується відповідною машиною.

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

Задача теорії розкладів вважається заданою, якщо визначені:

-роботи та операції, що мають бути виконані;

-кількість та типи машин, які виконують операцію;

-порядок проходження робіт;

-критерій оцінки розкладу.

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

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

Порядок виконання машинами операцій однієї роботи визначає, чи є система машин:

- конвеєрною;

- з випадковим порядком виконання робіт;

- системою довільного типу.

В конвеєрній системі послідовність проходження машин однакова для кожної з робіт.

Випадковість - це фактор, який визначає результат експерименту з множини можливих результатів, відомих заздалегідь. Тобто ми вважаємо, що експеримент має випадковий результат, якщо його кінцевий результат не може бути визначений апріорі з множини можливих варіантів.
Конвеєр (рос. конвейер, англ. conveyor; нім. Rutsche f, Stetigförderer m, Förderer m, Fließband n) – машина безперервної дії, призначена для транспортування насипних і штучних вантажів - корисних копалин, породи, закладальних матеріалів та інш.

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

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

Для класифікації задач теорії розкладів надалі використовується запис A/B/C/D, де:

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

Функція розподілу ймовірностей - В теорії ймовірностей це функція, яка повністю описує розподіл ймовірностей випадкової величини.

В характеризує кількість машин у системі. Якщо на місці B стоїть m, то це означає довільну кількість машин.

С характеризує порядок (дисципліну) виконання робіт машинами. Якщо на місці C знаходиться F, то це відповідає конвеєрній системі, якщо R- то випадковій, якщо G – то довільній системі. Для систем з однією машиною вказані дисципліни втрачають сенс, тому третій параметр опускається.

D характеризує оцінку (критерій) розкладу.

Наприклад, запис n/2/F/Fmax означає, що треба впорядкувати n робіт в конвеєрній системі, що складається з двох машин так, щоб мінімізувати максимальну тривалість проходження роботи (це так звана задача Джонсона).

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

Спочатку домовимось розрізняти вихідні та шукані величини задачі. Перші визначаються специфікою поставленої задачі, другі є результатом складання розкладу. Щоб підкреслити цю різницю, вихідні величини позначаються малими латинськими літерами (наприклад x,y,z), а шукані – великими (наприклад X, Y, Z).

Лати́нська абе́тка, або латиниця, латинка - абетка латинської мови, історично є відгалуженням етруської абетки, що в свою чергу постала з грецької. Виникнення латинської абетки датують 7 ст. до н. е. Напрямок письма: спочатку справа наліво, потім справа наліво й, через рядок, зліва направо (так званий бустрофедон), з 4 ст.
Нехай:

ri – момент готовності (момент надходження) i-ї роботи,

di - плановий (директивний) термін її виконання. Ця величина являє собою момент, не пізніше якого повинна бути виконана дана робота.

ai – допустима тривалість проходження i-ї роботи.

Між означеними величинами існує співвідношення di ri=ai, тому для кожної роботи достатньо задати дві з трьох означених величин.

Ti- момент завершення роботи i,

Fi- тривалість проходження роботи і в системі.

Часове зміщення роботи Li може бути визначено таким чином:


Li=Ti-di=Fi-ai. (2.1)
Визначимо запізнення Zi та упередження роботи таким чином:
Zi=max(0,Li), Fi=max(0,-Li). (2.2)
Часове зміщення, запізнення та упередження оцінюють фактичний час закінчення роботи порівняно з її плановим терміном. Часове зміщення кожної роботи може мати будь-який знак. Якщо воно додатне , тобто робота завершується після планового терміну, то воно дає значення запізнення, якщо від’ємне, тобто робота завершується до планового терміну, то модуль зміщення дає значення упередження.

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


. (2.3)

Де n – кількість робіт.

В теорії розкладів найчастіше використовуються такі критерії: середні, середньозважені та максимальні значення

- моментів закінчення робіт;

- тривалостей проходження;

- часового зміщення;

- запізнення;

- упередження;

- тривалості очікування.

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



- регулярний критерій, якщо то з цього випливає, що:

. (2.4)

Побудуємо математичну модель розкладу у вузі з використанням теорії розкладу[4]. Введемо позначення і визначимо змінні та обмеження [13].

У вузі є N навчальних груп, об'єднаних в R потоків; r - номер потоку, r = 1, ..., R, kr - номер навчальної групи в потоці r, kr = 1, ..., Gr.

Розбиття на груп на потоки здійснюється виходячи з принципів:

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

2. Група (або її частина), як одиниця навчального процесу у ВНЗ, може входити в різні потоки.

3. Кількість потоків не лімітується.

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

Лабораторія (середньовічна лат. laboratorium, від лат. laboro - працюю, лат. labor - праця, робота) - багатозначний термін, що залежно від контексту, може означати: Спеціально обладнане та устатковане приладами, пристроями, мережами приміщення або транспортний засіб (наприклад, автомобіль, вагон потягу, літак, гелікоптер, субмарина тощо) для наукових досліджень, навчальних робіт, контрольних аналізів та випробувань (див. лабораторне устаткування). Установу або її відділ, що проводить експериментальну науково-дослідницьку та навчальну роботу. Внутрішні творчі процеси, внутрішню діяльність кого-небудь. Наприклад, творча лабораторія дослідника, митця тощо.

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

позначимо:

t - номер робочого дня тижня,

t Є Tkr;

де,

Tkr - множина номерів робочих днів для групи kr;



j - номер пари, j = 1, ..., J;

J - загальна кількість пар в день;

К – кількість годин по дані дисципліні, що передбачено в програмі;

�� – множина значень які може прийняти перемінна.

З кожної навчальної групою kr потоку r протягом тижня, згідно з навчальним планом, проводиться Wkr занять, з яких Sr лекційних та Qkr семінарських (лабораторних або практичних).

Семінарія (від лат. seminarium - «розсадник») - навчальний заклад для підготовки християнського духівництва.
позначимо:

sr - номер дисципліни у списку лекційних занять для потоку r, sr = 1, ..., Sr;

qkr - номер дисципліни у списку практичних занять для групи kr, qkr = 1, ..., Qkr.

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

Викладачі

Нехай p - номер (ім'я) викладача, p = 1, ..., P. Введемо в розгляд булеві значення і :


(2.5)

= (2.6)
Навчальне навантаження викладачів планується до складання розкладу занять, внаслідок чого на даному етапі величини і можна вважати заданими. Для кожного викладача p, p = 1, ..., P, задана також його аудиторне навантаження - Np годин на тиждень.

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

Нехай D – множина дисциплін, тоді ND1 , ND2 …. NDn певна дисципліна кожної групи

Введемо в розгляд булеві значення і


(2.7)

(2.8)
Знайдемо список всіх лекційних дисциплін на потоці r і позначимо його .

(2.9)
Визначимо список унікальних дисциплін для кожної групи і позначимо його .
. (2.10)
На рисунку 2.1 зображено математичний алгоритм сортування дисциплін на унікальні для кожної групи та на дисципліни які є у списку лекційних занять для потоку.

Рисунок 2.1 - Алгоритм сортування дисциплін на унікальні для кожної групи та на дисципліни які є у списку лекційних занять для потоку

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

Інформа́тика (англ. Computer Science, нім. Informatik) - наукова дисципліна, що вивчає методи та процеси створення, перетворення, зберігання, передачі інформації та використання її в різних галузях людської діяльності.
Алгоритм сортування - це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів.
Практи́чні заня́ття - форма навчального заняття, при якій викладач організує детальний розгляд студентами окремих теоретичних положень навчальної дисципліни та формує вміння і навички їх практичного застосування шляхом індивідуального виконання студентом відповідно сформульованих завдань.
нехай:

{A1r} - множина аудиторій для лекцій на потоці r;

{A2r} - множина аудиторій для практичних занять на потоці r;

A1r - число елементів множини {A1r};

A2r - число елементів множини {A2r};

A1r A2r - число аудиторій об'єднання множин {A1r} ∩ {A2r}.

Аудиторний фонд визначається до початку складання розкладу, тому множини можна вважати заданими.

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

Введемо наступні шукані булеві змінні:
= (2.11)
= 2.12)
Для кожної групи kr повинні виконуватися всі види аудиторної роботи протягом тижня:

(2.13)




У будь-який день t на кожній парі j для кожної групи kr може проводитися не більше одного заняття:



(2.14)




Кожні лекція sr і практичне заняття qkr відповідно для всіх потоків r і всіх груп kr можуть проводитися не більше одного разу на будь-який день t:




(2.15)








Якщо змінні і пов'язують всі види занять з часом їх проведення, то вирази і пов'язують час проведення з іменем викладача.

В кожен день t і в кожній парі j викладач p може вести більше одного заняття по одній дисципліні на одному потоці або в одній групі:

(2.16)





Кожен викладач p протягом тижня повинен провести аудиторні заняття:



(2.17)

Нарешті, в кожен день на кожній парі число лекцій і практичних занять не повинно перевищувати наявний у вузі аудиторний фонд:



(2.18)

(2.19)





Крім того, для всіх сукупностей пересічних множин {A1r} і {A2r} повинні виконуватися умови:




(2.20)


Представленими співвідношеннями вичерпуються безумовні обмеження, з якими завжди вважаються при складанні розкладу

1   2   3   4   5   6   7   8   9



  • 2 МАТЕМАТИЧНА МОДЕЛЬ ПРОЦЕСУ ФОРМУВАННЯ РОЗКЛАДУ 2.1 Математична модель об‘єктів розкладу