Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Виникнення і етапи розвитку теорії розкладівДо 20-го століття вирішення завдань ТР не вимагало багато часу або великого числа обчислень. На початку минулого століття розвиток науки і техніки прискорилося. Збільшився темп і повсякденного життя. Завдання складання розкладів оперували все більшим кількість взаємопов'язаних робіт, і порядок їх у часі ставало все важче. На початок 20-го століття відносяться два показових прикладу. У період з 1903 по 1919 рр.. американський вчений Генрі Гантт публікує ряд наукових робіт і пропонує новий спосіб представлення розкладів, що отримав назву "Діаграма Гантта". Гантт займався дослідженням і поліпшенням керівництва (менеджменту) на промислових підприємствах (наприклад, у компанії з виробництва бавовняних тканин і на підприємствах з будівництва кораблів). Діаграма Гантта - це схематичне зображення календарного плану. Інший показовий приклад - винахід конвеєра Генрі Фордом. У 1908-му році він організовує потокове виробництво на своєму автомобільному заводі "конвеєрного типу". У даній інтерпретації конвеєр - це спосіб організації виробництва будь-яких виробів, при якій: • процес виробництва поділяється на окремі операції (стадії); • одночасно в провадженні знаходиться кілька виробів, що знаходяться на різних стадіях. Операції при такому способі виробництва впорядковані. Тобто існує черговість операцій і порушувати її не можна. Наприклад, не має сенсу прикручувати колеса або вставляти скла, поки не зібрана рама. Ще одна важлива особливість такого виробництва - виконання незалежних операцій паралельно. Тобто поки збирається кузов, паралельно на іншій лінії можна збирати двигун. Конвеєрне виробництво дозволило Форду в 1,5 рази скоротити час випуску автомобілів. Тепер конвеєр Форда можна зустріти на багатьох масових виробництвах. Отже, у першій половині 20-го століття був сформульований ряд практичних і теоретичних завдань складання розкладів. У 1956-му році Річард Беллман запропонував термін "Теорія розкладів" для позначення сукупності даних завдань та належних до них наукових знань. У 1967-му році публікується монографія Конвея, Максвелла і Міллера "Теорія розкладів". У 1975-му році переклад цієї книги на російську мову синхронно виходить з книгою радянських авторів В.С. Танаєва і В.В. Шкурба "Введення в теорію розкладів". З цього часу можна вважати ТР сформувалася теорією. У 70-х роках 20-го століття (після виходу робіт про теорію складності рішення оптимізаційних задач) акцент у дослідженні завдань ТР змістився. Тепер при вивченні завдань ТР дослідник не лише будує ефективні алгоритми рішення, а й шукає відповідь на питання - наскільки складна задача в термінах NP-труднощі і поліноміальної розв'язності, і який швидкості алгоритм "в кращому випадку" можна для цього завдання побудувати. Способи подання розкладів. · Раніше ми вже познайомилися з деякими способами подання розкладів. Позначимо головні з них. · Табличне подання. У таблиці представлені проміжки часу, в які виконуються завдання, а також їх виконавці (номер верстата, процесор і т.п.). · Графічне представлення. Наприклад, за допомогою Діаграми Гантта. · Для деяких завдань ТР можливо векторне (перестановочне) подання розкладу. При цьому вказується лише порядок виконання завдань, наприклад (2, 3, 4, 1).
|