Skip to main content
LibreTexts - Ukrayinska

7.2: Початок роботи

  1. Last updated
  2. Save as PDF
  • Page ID
    66487

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

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

    Завдання 1: Зняти деталі двигуна і газу (2 дні)

    Завдання 2: Паром очистити внутрішню частину автомобіля (0,5 дня)

    Завдання 3: Купити електродвигун і регулятор швидкості (2 дні для подорожі)

    Завдання 4: Побудувати деталь, яка з'єднує мотор з трансмісією автомобіля (1 день)

    Завдання 5: Побудувати акумуляторні стійки (2 дні)

    Завдання 6: Встановлюємо мотор (0,5 дня)

    Завдання 7: Встановлюємо регулятор швидкості (0,5 дня)

    Завдання 8: Встановлюємо стійки акумуляторних батарей (0,5 дня)

    Завдання 9: Провід електрики (1 день)

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

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

    Диграф

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

    Наприклад, цей диграф показує, що завдання 1, позначене\(T_1\) для компактності, має бути виконано перед завданням 2. Число в дужках після назви завдання - це час, необхідний для виконання завдання.

    sc1.svg

    Приклад 1

    Повний диграф для нашого перетворення автомобіля виглядатиме наступним чином:

    sc2.svg

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

    Процесори

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

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

    Час обробки

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

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

    clipboard_e38968d98b49af2415b5b701b1ecf6089.png

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

    Оптимальний графік

    Оптимальним графіком є графік з максимально коротким терміном обробки.

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

    clipboard_e93755d85ea732f6a49a9187f54818ad3.png

    З двома процесорами час обробки скоротився до 5,5 днів. Що робив процесор 2 протягом останнього дня? Нічого, тому що завдання процесору робити не було. Це називається простоєм.

    Час простою

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

    Чи оптимальний такий графік? Чи міг він бути завершений за 5 днів? Оскільки кожне інше завдання потрібно було виконати до початку завдання 9, не було б ніякого способу, щоб обидва процесори могли бути зайняті під час завдання 9, тому неможливо створити більш короткий графік.

    Так скільки часу займе, якщо ми використовуємо три процесори? Про\(10/3 = 3.33\) дні? Знову вгадаємо і перевіримо розклад:

    clipboard_ee949eace502f3be66e83458757477c80.png

    З трьома процесорами робота все ж зайняла 4,5 дня. Трохи складніше сказати, чи є цей графік оптимальним. Однак може бути корисно помітити, що оскільки завдання 1, 2, 6 та 9 повинні виконуватися послідовно, неможливо виконати цю роботу менш ніж за\(2+0.5+0.5+1 = 4\) дні, незалежно від кількості процесорів. Чотири дні - це, для цього диграфа, абсолютний мінімальний час для завершення роботи, який називається критичним часом.

    Критичний час

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

    Критичний час можна визначити, дивлячись на найдовшу послідовність завдань в диграфі, звану критичним шляхом