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

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



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

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




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

1.2 Аналіз відомих методів формування розкладу
Існує багато класичних методів розв’язання задачі складання розкладу. Так, модель задачі складання розкладу в рамках лінійного цілочисельного програмування містить ряд недоліків, пов’язаних як з неповною адекватністю представленого розв’язку задачі, так і значною трудомісткістю використання запропонованого комплексу програм, що вимагає участі кваліфікованого користувача. Метод імітації випалювання та алгоритм розфарбовування графу, незважаючи на зовнішню простоту, можуть виявитися цілком ефективними для складання лише невеликих розкладів. При реалізації алгоритму, що базується на принципах імітаційного моделювання, обмежується можливість застосування розробленої системи в інших ВНЗ, крім того, знадобиться вносити істотні зміни в алгоритм при незначних внутрішніх змінах у ВНЗ.
Випа́лювання (випалабо випалення) (рос. обжиг, англ. roasting, нім. Rösten n) - технологічна операція, яку проводять з метою надати матеріалам (руда, концентрати тощо) необхідних властивостей (фізичних, хімічного кладу) для подальшого перероблення нагріванням з витримкою без розплавлення хоча б одного твердого компонента матеріалу.
Принцип (лат. principium - начало, основа) - це твердження, яке сприймається як головне, важливе, суттєве, неодмінне або, принаймні, бажане. У повсякденному житті принципами називають внутрішні переконання людини, ті практичні, моральні та теоретичні засади, якими вона керується в житті, в різних сферах діяльності.
Усі ці методи в своїй основі використовують ітераційну техніку неперервної оптимізації. Очевидно, що вони орієнтовані на пошук лише локальних оптимумів, а глобальний оптимум може бути знайдений лише випадково. У зв’язку з цим раціонально використовувати методи, які зберігають переваги класичних і вільні від їх недоліків. До таких методів відносять еволюційне моделювання [5].

1.2.1 Генетичний алгоритм

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

Раціональність (від лат. Ratio - розум) - термін у найширшому сенсі означає розумність, свідомість, протилежність ірраціональності. У більш вузкому значенні - характеристика знання з точки зору його відповідності деяким принципам мислення.
Непере́рвна фу́нкція - одне з основних понять математичного аналізу. Неперервні функції трапляються набагато частіше, ніж диференційовні, множина всіх неперервних функцій замкнена відносно арифметичних операцій (за винятком ділення) і композиції та утворює чи не найважливіший клас функцій в аналізі.
Еволю́ція - природне явище зміни популяцій, видів, вищих таксонів, біоценозів, флор і фаун, генів і ознак у часі в ході історії Землі.
Генети́чний алгори́тм (англ. genetic algorithm) - це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.
Першим кроком при розробці математичної моделі є розробка структури хромосоми, в якій буде зберігатися розв’язок. У нашому випадку такою «хромосомою» є розклад. Обрана структура повинна враховувати всі особливості й обмеження шуканого розв’язку. На наступному кроці з хромосом формують початкову популяцію.
Хромосо́ма - це велика молекулярна структура, де міститься близько 90 % ДНК клітини. Всі хромосоми містять дуже довгий безперервний полімеризований ланцюг ДНК (єдину ДНК-молекулу), що містить гени, регуляторні елементи та проміжні нуклеотидні послідовності.
Популяція - сукупність організмів одного виду, що займають обмежений ареал (територія поширення якогось об'єкта або явища), мають спільне походження за фенотипом та географічно ізольовані від інших популяцій даного виду, можуть вільно схрещуватися і дають плодюче потомство.
Для створення нового покоління з кращими показниками із сукупності хромосом необхідно вибрати кращі для подальшої репродукції.
Репроду́кція (лат. re- префікс, що означає зворотню або повторну дію і лат. produco - створюю) - відтворення.
Відбір хромосом здійснюється за допомогою цільової функції, яка визначає ступінь придатності хромосоми до формування наступного покоління. Щоб отримати нову популяцію, відібрані хромосоми попарно схрещують між собою, після чого до популяції застосовують оператор мутації. Після реалізації мутації цільова функція перераховується і все починається спочатку.

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


1.2.2 Нейроний підхід при створені розкладу

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

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

В даний час для вирішення задачі складання розкладу застосовується ще один новий підхід нейронні мережі [7].

Штучна нейронна мережа (ШНМ, англ. artificial neural network, ANN, рос. искусственная нейронная сеть, ИНС) - це математична модель, а також її програмна та апаратна реалізація, побудовані за принципом функціювання біологічних нейронних мереж - мереж нервових клітин живого організму.
Найважливішим недоліком застосування цього підходу є складність вибору початкового стану нейронної мережі. В останні роки особливого поширення набули дослідження методів еволюційного пошуку [8,9].
1.3 Інформаційні технології складання розкладу на основі теорії розкладів
“Часовий” метод розвязку задач теорії розкладів (ТР) виділяє характер задач в особливий клас, що істотно відрізняється від “об’ємних” або кошторисних економічних задач. Якщо для економічних задач треба визначити, що і в якому обсязі треба виробляти, то для задач ТР треба визначити, коли і в якій послідовності треба виконувати задані роботи. Ця різниця в постановках задач визначає різницю в методах їхнього розв’язку. Для економічних задач існує математичній апарат, який дозволяє більш чи менш успішно їх розв’язувати. Для задач ТР математичний апарат розвинутий в значно меншій ступені.
Ви́ділення (екскреція) - процес виведення кінцевих продуктів, які утворилися в ході обміну речовин в клітинах тіла при розщепленні органічних енерговмісних речовин. Цю функцію виконують як спеціалізовані видільні органи, так і інші органи чи системи, для яких видільна функція може бути побічною, другорядною.
Матема́тика (грец. μάθημα - наука, знання, вивчення) - наука, яка первісно виникла як один з напрямків пошуку істини (у грецькій філософії) у сфері просторових відношень (землеміряння - геометрії) і обчислень (арифметики), для практичних потреб людини рахувати, обчислювати, вимірювати, досліджувати форми та рух фізичних тіл.
В ТР часто кожна задача вимагає індивідуального підходу. Підходи до пошуку оптимального розкладу можна умовно розбити на 4 типи:

- математичне програмування;

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

- комбінаторний підхід;

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

- вристичний підхід;

- ймовірнісно-статистичне моделювання;

Далі розглянемо в загальних рисах означені підходи [9,10].

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

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

Спочатку нагадаємо визначення таких понять, як задачі класу Р, ефективні алгоритми та NP повні задачі.

Алгоритм називається ефективним, для якого кількість елементарних кроків зростає як поліном від розмірності вихідної задачі. Задачі, що мають ефективні (поліноміальні) алгоритми розв’язку, належать до класу P- задач. Будь-яку NP - повну задачу не можна розв’язати ніякими відомими поліноміальними алгоритмами.

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

Для NP- повних задач вводиться поняття поліноміального алгоритму їхнього розв’язку, який має задовольняти наступним умовам:

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

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

- поліноміальний алгоритм є ефективним та статистично значимим, тобто при моделюванні індивідуальних задач істотна частка розв’язків є точними [12].

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

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

Ймові́рність (лат. probabilitas, англ. probability) - числова характеристика можливості того, що випадкова подія відбудеться в умовах, які можуть бути відтворені необмежену кількість разів. Імовірність є основним поняттям розділу математики, що називається теорія імовірностей.
Міркування - зіставлення думок, пов’язання їх задля відповідних висновків, логічне мислення. Можна розглядати міркування як аналіз і синтез даних, та їхню оцінку. Хоча знання фактів і є точкою відліку у вивченні суспільних наук, людина також повинна мати здатність до логічного мислення-міркування, адже саме міркування наповнює факти, проблеми і поняття змістом: міркуючи над засвоєним знанням, людина приходить до повнішого розуміння предмета. Міркування є також предметом логіки, яка вказує нам правила, закони або норми, яким повинне підкорятися наше мислення для того, щоб бути істинним.

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

Іншим напрямком евристичних методів в ТР є формування функцій переваг (пріоритетів). Для кожної i-ї роботи обчислюється значення функції fi переваги та вибирається та робота, для якої fi досягає мінімуму чи максимуму. Розглянемо деякі правила переваг:

- правила SPT/LPT (Shortest/Longest processing time). Перевага віддається роботі (операції) з множини готових до виконання на машині, що звільнилася, в якій час виконання на цій машині є мінімальним/ максимальним.

- правило SRT/LRT (Shortest/Longest remaining time). Перевага віддається роботі, для якої сума часів виконання залишкових робіт є найменшою/найбільшою [13].

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

Альтернати́ва (фр. alternative, рос. альтернатива, англ. alternative, нім. Alternative) -
Цей принцип може бути застосований як при знаходженні початкового розкладу, так і на етапі його дальшого покращення (наприклад, згаданим вище шляхом локального пошуку).

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

Перевагою евристичних методів є зручність їхньої реалізації на ЕОМ навіть при розв’язку громіздких задач.

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

Оцінювання - (фр. evaluation від value ціна, вартість) оцінка, визначення ціни, вартості, визначення кількості, якості продукції, якості ресурсів, придатності тощо; аналіз даних, обстановки.
Крім того, для кожного з наведених евристичних алгоритмів існують задачі, для яких застосування означених алгоритмів дає погані результати.

Ймовірнісні методи пов’язані з к-кратним моделюванням розкладів. Після цього вибирається найкращий розклад, який приймається за наближений розв’язок задачі [14].

Далі розглянемо деякі задачі теорії розкладів.

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

Розглянемо систему n/1. Для даної системи зробимо такі припущення:

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

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

Момент часу - точка на часовій осі. Про події, що відповідають одному моменту часу, говорять як про одночасні.

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

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

Теорема 1. Для системи n/1 розклад, оптимальний відносно регулярного критерію, належить класу, що виключає переривання та штучні простої.

Доведення:

- випадок штучних простоїв.

Розглянемо розклад S, який містить простої на відрізку від t1 до t2,

де 0< t12max (рисунок 1.1).







0







t1 t2




Tmax

S








































S’


















Рисунок 1.1 – Розклад який містить простої


Нехай розклад S’ відрізняється від розкладу S тим, що машина не простоює на відрізку [t1;t2] і всі події, що відбуваються після t2, випереджають відповідні події S на t2-t1. При цьому, очевидно, не змінюються моменти завершення робіт, які закінчились до моменту t1, а для робіт, що закінчуються після t2 моменти закінчення для S’ зсуваються вліво на t2-t1 і отже Ti’-Ti, i=1,2,...,n. Таким чином, значення регулярного критерію для S’ не перевищує його значення для S, тому оптимальний розклад належить до класу без простоїв.

- Випадок наявності переривань.

Розглянемо розклад S, при якому робота I починає виконуватись в момент t1 і в момент t2, перед її закінченням переривається роботою J. (Для спрощення міркувань припустимо, що J не переривається). В момент часу t3 виконання роботи I знову поновлюється і триває до її завершення (рис.2).





0




t1

t2

t3







S

























0




t1













S’



















Рисунок 1.2 - розклад S, при якому робота I починає виконуватись в момент t1 і в момент t2


Тепер розглянемо розклад S’, який відрізняється від S тим, що першою з робіт I та J виконується робота I. Порівнюючи розклади S та S’, маємо, що В розкладі S’ робота J закінчиться раніше, ніж в S, а моменти закінчення інших робіт співпадають. Тому значення будь-якого регулярного критерію для S’ не перевищує відповідного значення для S. Якщо в розкладі S’ виконання роботи I переривається іншими роботами, то можна повторювати аналогічні процедури перестановки перериваючих робіт перед I доти, доки робота I не буде виконуватись без переривань.
Анало́гія - (грец. αναλογια - «відповідність») - подібність, схожість у цілому відмінних предметів, явищ за певними властивостями, ознаками або відношеннями.
В результаті всіх цих перестановок значення регулярного критерію не збільшується. З цього випливає, що оптимальний розклад належить до класу S’, тобто до класу, що не містить переривань.

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

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

Квадра́т - чотирикутник, у якого всі сторони рівні і всі кути прямі. Для задання квадрата необхідно і достатньо задати дві точки на координатній площині, які відповідатимуть будь-яким двом кутам та врахувати їх суміжність.
Наприклад [1] означає номер роботи що виконується першою, [2]=3 означає, що друга робота виконується третьою, t[1] означає тривалість роботи, яка виконується в першу чергу. Таким чином, для перестановочного розкладу
та . (1.1)
Відзначимо, що для перестановочних розкладів в системі n/1 максимальний час проходження робіт однаковий для всіх n!
Проходження (в астрономії) - видиме пересування небесного тіла на тлі видимого диска іншого.
Можливих розкладів і дорівнює сумі тривалостей всіх робіт [16].

Впорядкування по мінімуму тривалостей робіт

Розглянемо такий порядок виконання робіт, що
. (1.2)

Надалі таке впорядкування будемо називати впорядкуванням по мінімуму тривалостей робіт (shortest processing time sequencing) або, скорочено, SPT.

Абревіатура (лат. abbrevio - скорочую) - складноскорочені слова, похідне слово, що виникає внаслідок абревіації - утворення з перших літер або з інших частин слів, що входять до складу назви чи поняття.

Теорема 2. Середній час проходження робіт в системі n/1 мінімальний, якщо після впорядкування тривалості робіт не спадають:

, (1.3)

і максимально, якщо тривалості робіт не зростають:



. (1.4)

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



. (1.5)

Тоді середня тривалість проходження робіт дорівнює



(1.6)

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

Оскільки коефіцієнти (n-i 1) зменшуються з ростом i, то мінімум середньої тривалості досягається тоді, коли ti з ростом i зростають або принаймні не спадають.

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

Існує багато критерієв оцінки розкладів для системи n/1, згідно з якими впорядкування SPT не буде оптимальним. Найбільш важливі з них залежать від планових термінів, але й в цьому випадку розклад SPT може бути корисним. Так, якщо d1=d2=...=dn, то SPT мінімізує кількість робіт, що спізнились.

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

Приклад 1. Розглянемо систему 3/1/∑Zi з вихідними даними, наведеними в таблиці 1.

Таблиця 1.1 – Система 3/1/∑Zi з вихідними даними


робота

ТРИВАЛІСТЬ

плановий ТЕРМІН

a

3

3

b

1

4

c

2

2

Критерієм оцінки рокладу є:

. (1.7)
При цьому наведений критерій є регулярним. Всі 6 можливих послідовностей виконання робіт наведено на рис. 1.3. На цьому рисунку лінії з’єднують послідовності, що відрізняються одна від одної попарною перестановкою сусідніх робіт, кожна з послідовностей має два з’єднання.
Гра́фіка (нім. Graphik, грец. graphikos «написаний») - вид образотворчого мистецтва, для якого характерна перевага ліній і штрихів, використання контрастів білого і чорного та менше, ніж у живописі, використання кольору.
Розклад оцінюється сумарним запізненням всіх робіт (число внизу).

______ ______

 


 

______ ______

Рисунок 1.3 - 6 можливих послідовностей виконання робіт

В таблиці 1.2 наведені запізнення робіт у всіх розкладах.

Таблиці 1.2 – Запізнення робіт у всіх розкладах









S(b,a,c)







S(a,b,c)







S(a,c,b)







b

a

c

a

b

c

a

c

b

ti

1

3

2

3

1

2

3

2

1

Ti

1

4

6

3

4

6

3

5

6

di

4

3

2

3

4

2

3

2

4

Zi

0

1

4

0

0

4

0

3

2

Si

5

4

5

Ni

2

1

2

Якщо вибрати S(a,b,c) вихідним розкладом, то не існує попарної перестановки, яка покращує розклад і можливості метода попарних перестановок буде вичерпано раніше, ніж буде знайдено оптимальний розклад S(c,b,a). Справа в тому, що даний критерій не є транзитивним. Дійсно, з порівняння S(b,a,c), 5 та S(a,b,c), 4 випливає, що a повинна передувати b. З порівняння S (a,b,c), 4 та S(a,c,b), 5 випливає, що b повинна передувати c. Взагалі, взаємне розміщення двох робіт залежить від розміщення третьої. Так, якщо с є третьою роботою, то a повинна передувати b, ящо першою або другою, то b повинна передувати a.

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

Аспект (лат. aspectus - вигляд, погляд) - поняття філософії (онтології, теорії пізнання). У філософії аспект розглядається
Хоча коефіцієнт використання машин або тривалість проходження робіт є безумовно важливими характеристиками, однак, порівняно з ними критерій своєчасного виконання робіт є більш важливим.

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

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


(1.8)
Теорема 3 (Джексон). Розклад, що мінімізує максимум запізнення робіт в системі n/1 такий, що роботи виконуються в неспадному порядку виконання планових термінів.

Доведення. Нехай S*-розклад, в якому роботи виконуються в неспадному порядку планових термінів d[i], L*-відповідне значення максимуму запізнення, S – деякий розклад, відмінний від S*, отже, в S існує деяке i, для якого d[i]>d[i 1]. Порівняємо розклад S та розклад , що відрізняється від нього лише порядком проходження i-ї та (i 1)-ї робіт. В першому випадку маємо:


L=max[(t[1]-d[1]),…,(t[1] … t[i-1]-d[i-1]),(t[1] … t[i]-d[i]), (t[1] … t[i 1]-d[i 1]),

(t[1] … t[i 2]-d[i 2]),…, (t[1] … t[n]-d[n])]. (1.9)


Розглянемо відповідне значення L’ для альтернативного розкладу. В L’ всі елементи, що стоять під знаком максимуму, крім і-го та (і 1)-го співпадають з відповідними елементами L. Іншими словами, перестановка і-ї та (і 1)-ї вплинула лише на їхній термін проходження і не вплинула на термін проходження робіт [1],…,[i-1],[i 2],…,[n].
L (t[1] … t[i]-d[i]) , (t[1] … t[i] t[i 1]-d[i 1]), (1.10)
L’ (t[1] … t[i-1] t[i 1]-d[i 1]), (t[1] … t[i] t[i 1]-d[i]). (1.11)
Оскільки за припущенням d[i]>d[i 1], то член (t[1] … t[i] t[i 1]-d[i 1]) більше кожного з трьох інших, і оскільки береться операція взяття максимуму, то L≥L’. При переході до розкладу S* шляхом попарних перестановок сусідніх робіт, для яких d[i]>d[i 1], маємо ланцюжок нерівностей для максимальних значень запізнень L*≤… L’ ≤L, отже L*≤… L’≤L.
Нерівність - твердження про те, що два математичні об'єкти є різними, тобто не дорівнюють один одному. Для елементів упорядкованих множин нерівність може додатково стверджувати, що один із двох елементів менший або більший від іншого.

Теорема Джексона дозволяє по заданих величинах {ti},{di} відповідати на запитання, чи існує розклад, при якому немає жодного запізнення. Дійсно, якщо впорядкування згідно планових термінів дає нульове значення максимуму запізнення, то не запізнюється жодна робота і таким чином це є шуканим розкладом. Якщо максимум запізнення більший нуля, то він буде залишатись додатнім для будь якого іншого розкладу, отже, розкладу без запізнень не існує.

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

Дина́міка (грец. δύναμις - сила) - розділ механіки,в якому вивчаються причини виникнення механічного руху. Динаміка оперує такими поняттями, як маса, сила, імпульс, момент імпульсу, енергія.
Нехай в системі вже є n робіт, що виконуються в порядку S* і нехай в систему намагається надійти робота з заданими характериcтиками tn 1, dn 1. Виникає питання, за яких умов ця робота може бути допущеною машиною так, щоб побудувати новий розклад без запізнень. Нехай і* - максимальний індекс, такий що di*≤dn 1 Тоді згідно теореми Джексона роботу (n 1) треба поставити між роботами і* та (і* 1). Це ніяк не вплине на хід виконання робіт з 1 по і*, а термін проходження робіт з (і* 1) по n збільшиться на величину tn 1. Позначимо bi=ai-Ti запас часу при виконанні i-ї роботи (тобто максимальна величина збільшення часу проходження роботи, що не спричинить її запізнення). Таким чином, для того, щоб у новому розкладі не спізнилась жодна з робіт, потрібно виконання умови tn 1 ≤ min(bi), i=(і* 1),n. Виконання роботи (n 1) почнеться в момент Ti* та закінчиться в момент Ti* tn 1 і таким чином для того, щоб робота (n 1) не спізнилась, потрібно виконання умови Ti* tn 1≤dn 1. Таким чином, умова надходження нової роботи, яка не спричинить запізнення в системі має вигляд
Tn 1 ≤ min[min(bi), i=(і* 1),n; dn 1- Ti*]. (1.12)
В наступному прикладі розглянемо побудову області допуску нової роботи в декартовій системі координат.
Система координат - спосіб задання точок простору за допомогою чисел. Кількість чисел, необхідних для однозначного визначення будь-якої точки простору, визначає його вимірність. Обов'язковим елементом системи координат є початок координат - точка, від якої ведеться відлік відстаней.

Приклад 2. Нехай в початковий момент часу є три роботи з заданими величинами (ti,di) = (5,6) , (2,9) та (1,12).Впорядкуємо роботи в порядку зростання di, занесемо вихідні дані до таблиці 1.3 та розрахуємо величини


та bi=di-Ti. (1.13)
Таблиця 1.
Хеш-таблиця - структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і здійснювати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення за ключем.
3 – Впорядкування роботи в порядку зростання

i

di

ti

Ti

bi

1

6

5

5

1

2

9

2

7

2

3

12

1

8

4
1   2   3   4   5   6   7   8   9



  • 1.3 Інформаційні технології складання розкладу на основі теорії розкладів “Часовий” метод розвязку задач теорії розкладів (ТР) виділяє