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

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



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

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




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

Даний розклад є розкладом без запізнень. Дійсно, Ti≤di, i=1,2,3. Нехай в нульовий момент часу намагається надійти ще одна робота. Знайдемо множину всіх пар значень (t,d), для яких ця робота може бути прийнята в систему без виникнення запізнень та зобразимо цю область в декартовій системі координат.


1) , (1.14)

2) , (1.15)

3) , (1.16)

4) . (1.17)



Рисунок 1.4 - шукана область значень D


На рисунку 1.4 зображена шукана область значень D. При цьому виявилось більш зручним відкладати a вздовж осі абсцис, а t – вздовж осі ординат.

Нехай нова робота надходить не в нульовий, а в деякий інший момент часу r (випадок неодночасного надходження робіт буде розглянуто нижче). Тоді область допустимих значень D(t,a) можна одержати з вихідної області зсувом на r одиниць вліво та відкиданням всіх точок, що опиняться за межами кута L0a. Таким чином, через 12 одиниць часу і надалі область D буде співпадати з кутом L0a. Це можна зрозуміти і з інших міркувань. На момент часу r=12 всі три роботи будуть виконані і не будуть заважати додатковій роботі. Єдина вимога, що залишається, це те, щоб час виконання роботи не перевищував максимальної тривалості її проходження, тобто t≤a.

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

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

Розглянемо порядкування згідно резерву часу. Інформацію, що міститься в наборі величин {di} можна врахувати іншим чином, а саме зробимо впорядкування згідно резервного часу кожної роботи. Резерв часу роботи i в момент часу t дорівнює величині di-ti-t і являє собою максимально допустиму тривалість очікування початку роботи, що не спричинить її затримки. Робота з мінімальним резервом часу має більше шансів бути затриманою, тому при впорядкуванні вона повинна мати пріоритет.

Пара́метр (від дав.-гр. παραμετρέω) - відмірюю, розмірюю)(рос. параметр, англ. parameter, нім. Parameter m, Kennwert m, Kenngrösse f, Kennzahl f) - величина, що нею характеризують якусь властивість, стан, розмір або форму об'єкта, робочого тіла, процесу, явища або системи тощо.
Пріоритет (рос. приоритет, англ. priority, нім. Priorität f) -
Оскільки доданок t є спільним членом для всіх робіт, то впорядкування має бути таким:


. (1.18)
На перший погляд здається, що впорядкування такого виду є деяким покращенням розкладу згідно планових термінів. Однак має місце досить несподіваний результат, що міститься в наступній теоремі.

Теорема 4 . Розклад, що максимізує мінімальне запізнення робіт в системі n/1 такий, що роботи виконуються у неспадному порядку резерву часу.

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

Крок 1. Впорядкувати роботи в порядку зростання планових термінів (Розклад S). Якщо при цьому кількість запізнень дорівнює 0 або 1, то це і є оптимальний розклад.

Крок 2. Нехай кількість робіт, що спізнюється при порядку зростання планових термінів дорівнює 2 або більше. Нехай k це мінімальний номер позиції роботи, що спізнюється. Серед робіт, номер позиції яких не перевищує к, вибираємо ту, що має максимальну тривалість, “позначаємо” та ставимо на останню позицію. Ці дії повторюємо доти, доки не залишиться жодної непозначеної роботи, що не спізнюється. Одержаний таким чином розклад має мінімальну кількість робіт, що спізнюються.

Приклад 3. Візьмемо дані з прикладу 1. В даному разі S=(c,a,b) –розклад з впорядкуванням в неспадному порядку планових термінів. При цьому кількість запізнень дорівнює 2 (запізнюються роботи a та b, с виконується вчасно), максимальна величина запізнення дорівнює 2 (отже не існує розкладу без запізнень). Першою роботою зліва, що запізнюється, є a. Вона має більшу тривалість, ніж с (нагадаємо, що ta=3, tc=2). Позначаємо роботу a, ставимо її на останнє місце, і таким чином переходимо до розкладу S’=(c,b,a) . В цьому розкладі немає непозначених робіт, що не запізнюється, отже, це є оптимальний розклад згідно даного критерію. При цьому, мінімальна кількість запізнень дорівнює 1, що підтверджує табл. 2.

Однак, немає впорядкування, яке мінімізувало б сумарне запізнення (S-критерій) робіт. Ця задача належить до класу NP-повних. Але наступні міркування іноді дозволяють зменшити кількість варіантів перебору і визначити “перспективну” множину розкладів, серед яких слід шукати оптимальний.

Введемо на множині робіт наступне відношення частинного порядку. Будемо вважати i"≤”k якщо titk та didkтривалість роботи , і директивний термін виконання не більші).

Теорема 5. Серед оптимальних розкладів згідно критерію сумарного запізнення існує такий, що для будь-якої пари робіт, такої, що i"≤”k має місце [i]<[k] (i-та робота виконується раніше k-ї).

Доведення. При доведенні теореми скористаємось допоміжним твердженням. Нехай f(x) – опукла вниз функція. Тоді для довільних x0 справедлива нерівність f(x) f(y)≤f(x-t) f(y t) (довести самостійно).

Нехай titk та didk та i-та робота виконується після k-ї. Розглянемо альтернативний порядок виконання робіт, міняючи місцями i-ту та k-ту роботи (при цьому між ними можливо є інші роботи). Нехай Ti, Tk-терміни виконання робіт при вихідному порядку, тоді Ti=Tk-tk ti, Tk=Ti -терміни виконання робіт при альтернативному порядку. Покажемо, що альтернативний порядок не гірший за S-критерієм, ніж вихідний. Оскільки в вихідному порядку i-та робота виконується після k-ї, то Ti,>Tk.

Доведемо наступну нерівність


(Ti-di) (Tk-dk) ≥ (Tk-tk ti-di) (Ti-dk) (1.20)
Скористаємось допоміжним твердженням і покладемо f(x)=x =max(x,0), x=min[(Tk-di), (Ti-dk)] , y=max [(Tk-di), (Ti-dk)] ,t=(Ti-di)-y=x-(Tk-dk), звідки безпосередньо випливає (1). З (1) випливає нерівність (2)
(Ti-di) (Tk-dk) ≥ (Tk-di) (Ti-dk) (1.21)
на підставі якої робимо висновок, що при альтернативному розкладі сумарний час запізнення і-ї та к-ї робіт не збільшиться.

Розглянемо інші роботи. В результаті заміни місць і-ї та к-ї робіт час проходження робіт, що знаходились в вихідному розкладі перед k-ю або після і-ї не змінився, отже не змінилася величина запізнення (Tj-dj) . Час проходження робіт, які знаходились між k-ю та і-ю роботами зменшився на величину tk-ti, отже їхні величини запізнень зменшились (якщо вони були додатніми) або принаймні не змінились (якщо були нульовими). Таким чином, при переході до альтернативного розкладу значення критерію не збільшилось. Роблячи послідовні заміни робіт, що задовольняють нерівність "≤” одержуємо розклад, що задовольняє умові теореми.

Приклад 4. Візьмемо дані з прикладу 1. с"≤"a, тому будемо розглядати лише розклади, в яких с передує a, тобто bca, cba та cab (яким відповідає нижній рядок графа та нижня половина табл.2). Розклад cba є оптимальним, а від двох інших розкладів можна перейти до cba заміною сусідніх елементів.

Зауваження. Результати теореми 5 не розповсюджуються на випадок критерію кількості робіт, що спізнились. Це демонструє наступний приклад.

Приклад 5. Нехай ta=3, da=2, tb=6, db=8. Тоді a"≤"b. При розкладі (a,b) роботи а та b спізнюються на 1, а при розкладі (b,a) робота b не спізнюється, але a спізнюється на 7. Таким чином, розклад (a,b) виявляється кращим за критеріями Z та S, але гіршим за критерієм N.

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

Переміщення - зміна положення якогось матеріального об'єкту. В фізиці - це переміщення фізичного тіла. Переміщенням також називають вектор, який характеризує цю зміну. Має властивість адитивності. Абсолютна величина переміщення, тобто довжина відрізка, що сполучає початкову й кінцеву точку, вимірюється в метрах у системі СІ та в сантиметрах у системі СГС.

Теорема 6. Якщо для системи n/1 існує таке впорядкування, що максимальне запізнення дорівнює 0, то існує і впорядкування з роботою К в останній позиції, яке зберігає нульовим максимальне запізнення і одночасно мінімізує середню тривалість проходження тоді і тільки тоді, коли
(1.22)
(робота виконується останньою, якщо це не приводить до її запізнення),

б) tk≥ti для всіх таких i, що


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

Доведення. Розглянемо розклад S з такими властивостями: максимальне запізнення дорівнює нулю та робота K, що виконується останньою, задовольняє умовам а), б) теореми.

Покажемо, що будь-яке переміщення роботи K з останнього місця приводить до запізнення та/або збільшенню середньої тривалості проходження.

Спочатку відзначимо, що не існує іншої роботи J, яка виконується раніше, ніж K та задовольняє умовам а) та б) теореми, якщо тільки не tj=tk (Якщо tj=tk, то байдуже, яка з робіт виконується останньою).

Якщо J не задовольняє умові а) теореми, то її перестановка з K приводить до ненульового запізнення для J, що протирічить умовам теореми.

Якщо не задовольняє умові б), тобто tjk, то пе6рестановка J з K приведе до зростанню сумарної тривалості проходження робіт на величину



ν(tj-tk), де ν – різниця номерів позицій робіт J та K.

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

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

Крок 2. Знаходиться час закінчення роботи [n-1] за формулою


(1.24)
Далі з сукупності робіт, для яких планові терміни більші або дорівнюють T[n-1] вибирається робота максимальної тривалості. Ця робота виконується [n-1] та викреслюється зі списку робіт.

Крок 2 повторюється n-1 разів і послідовність робіт у розкладі будується “справа наліво”.



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

Microsoft Excel. Практичне впровадження планування навчального процесу з використанням веб-технологій має місце лише в небагатьох вузах. Аналіз стану цих розробок дозволяє зробити наступні висновки:

- Розробка та впровадження вузами задач АСУ здійснюється в ініціативному порядку і ці роботи, як правило, спрямовані на вирішення окремих проблем. Роз'єднаність груп дослідників і розробників привела до створення безлічі систем, спрямованих на розробку алгоритмів і програм, розрахованих на обслуговування тільки конкретного вузу[15].

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблиця 1.4 – Програми формування розкладу


Системи складання розкладу занять

Назва

Коротка характеристика

Ціна

«Ректор» ver 3.0 Москва - ЛИнТеч


DOS; тільки школи і коледжі; до трьох тижнів без дат; до 100 класів

600 грн.

«Пенал» ИКФ ТРИССТАР

DOS; один тиждень, тільки школи

1049 грн

«Myschool» всеукраїнська навчальна екосистема

Windows, один тиждень, тільки школи

750 грн.

«Расписание 1.1» м. Уфа

Windows, один тиждень, тільки школи, без обмеження розміру

650 грн.

«Schedule» м. Київ

DOS; один тиждень, тільки школи

750 грн.

«Методист»

Windows, школи, вузи

7624 грн

«АВТОР-2 ver 9.9» м.Ростов

DOS; (без обмеження розміру) школи, вузи

Від 3000

до 9000 грн



«Расписание » ИнфоЦентр м. Абакан

DOS; один тиждень, школи, вузи

3000 грн.

«Расписание 2000» Микола Цигуро

Windows, DOS, школи, ліцеї, технікуми, без обмеження розміру

1500 грн.

«Ніка» НікаСофт

Windows, школи, ліцеї, гімназії, один тиждень

2500 грн

«Gelcat» Англія

Windows, коледжі, вузи

6500 грн.
1   2   3   4   5   6   7   8   9



  • 1.4 Аналіз відомих програм та вибір аналогу