Головна

Завдання обслуговування заявок на одному приладі

  1. IV. Особливості продажу товарів в підприємствах (відділах, секціях) самообслуговування
  2. Аварії на водному транспорті
  3. Алгоритми обробки одновимірних числових масивів
  4. Аналіз послуг системи дистанційного банківського обслуговування, що надаються фізичним особам
  5. Базисні умови поставки в міжнародному контракті купівлі-продажу, їх призначення та види Лукін А. Ю.
  6. Чи буде зберігатися енергія E, імпульс, момент імпульсу і при вільному русі частинки?
  7. Купуватиме. Це впливає на те, яку саме стратегію подачі заявок ви-

Це найпростіша задача теорії розкладу.

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

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

Завдання обслуговування набуває вигляду:

(2)

Хоча можливий повний перебір, але він не є раціональним. Оптимальний план можна отримати методом варіацій.

Визначення. Найпростішою варіацією перестановки  називають таку перестановку  , У якій в порівнянні з  переставлені місцями дві сусідні заявки и .

, .

Підрахуємо, на скільки зміниться штраф при переході від к  . маємо:

Припустимо, що  виявилася оптимальною перестановкою  . Це означає що

(3)

(3) - необхідна умова оптимальності  , А так як у завдання існує оптимальний план, то це необхідна умова буде і достатнім, тобто будь-яка послідовність, яка задовольняє (3) буде оптимальною.

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

Розглянемо окремий випадок, коли для всіх заявок штраф однаковий.

.

Тоді скоротивши в (3) чисельник на цю загальну величину, отримаємо критерій оптимальності:

, (4)

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

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


 



МЕТОДИ ПОШУКУ | Метод гілок і меж. Загальна схема Завдання про рюкзаку

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

© um.co.ua - учбові матеріали та реферати