Статьи по экономическим темам
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

ОПТИМІЗАЦІЯ РОЗПОДІЛУ РЕСУРСІВ  ПРИ КАЛЕНДАРНОМУ ПЛАНУВАННІ  БАГАТОНОМЕНКЛАТУРНОГО ВИРОБНИЦТВА.

Розглянемо один з найскладніших варіантів постановки задачі календарного планування, а саме планування багатономенклатурного виробництва (індивідуальне виробництво в машинобудуванні, судоремонт, дослідно-конструкторське виробництво і т. п.). Процес виконання кожного замовлення представлений у вигляді сітьового графа, в якому кожна робота може виконуватися з використанням кількох видів ресурсів. Для визначеності розглядатимемо трудові ресурси — робочих різних спеціальностей.

Нехай на підприємстві виконується N (n = 1, 2 … N) замовлень різними підрозділами (цехами, бригадами). По l-му (l = 1, 2 … L) підрозділу відома чисельність спеціалістів р-ї (р = 1, 2 … Р) професії.

Представимо процес виконання робіт п-го замовлення у вигляді сітьового графа Gn{Mn, An}, де Mn — сукупність вузлів, а
An — множина дуг, що з’єднують вузли графа. Кожна дуга графа Gn є однією з робіт п-го замовлення.

Припустимо, що для виконання кожної роботи (і, j) сітьового графа комплектується група з різних спеціалістів у кожному підрозділі , де — кількість спеціалістів р-ї професії в l-му підрозділі, що входять до к-ї групи, для виконання роботи (і, j).

Склад групи вважатимемо оптимальним, якщо вона виконує роботу (і, j) за мінімальний час . Через позначимо директивний строк виконання п-го замовлення.

Визначимо календарний план як сукупність упорядкованих у часі чисел , де — відповідно момент початку та закінчення роботи (і, j).

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

Оцінимо діяльність кожного спеціаліста певною кількістю балів bp. Тоді діяльність спеціалістів р-ї професії в l-му підрозділі
к-ї групи при виконанні роботи (і, j) визначається кількістю балів. Звідси діяльність кожної групи спеціалістів при виконанні роботи (і, j) можна оцінити сумарною кількістю балів

, (1)

причому для оптимального складу групи ця оцінка є найбільшою

. (2)

Логічно припустити існування і найменшої оцінки .

Тоді

, (і, j) Gn. (3)

Якщо робота виконується єдино можливим складом групи, вираз (3) перетворюється на рівність.

Визначимо ступінь збільшення тривалості виконання роботи (і, j) за рахунок неоптимальності складу групи параметром

, (4)

який змінюється в сегменті .

Величина визначає інтенсивність виконання роботи (і, j).

Тривалість tij виконання роботи (і, j) визначається формулою

. (5)

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

Графи замовлень, для яких , назвемо кращими.

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

Сукупність усіх робіт, які за сітьовим графом можна виконувати одночасно в момент t, назвемо фронтом робіт Ф (t). В один фронт робіт можуть входити лише роботи, що належать різним шляхам сітьового графа.

Об’єднаємо множину джерел графів Gn у вузол S шляхом введення допоміжних дуг ( ), де номер джерела п-го графа, а множину стоків — у вузол Т шляхом уведення допоміжних дуг ( ), де — номер стоку графа Gn. Отримаємо розширений граф G*.

У графі G* є дуги, відмічені ознакою подвійної критичності (їх множину позначимо через К2), а також такі, що відмічені одинарною ознакою критичності (К1). Окрему множину створюють дуги, не помічені ознакою критичності.

Згідно з [1] уведімо поняття замикання всередині сітки. Якщо х Î К2, у Î К2, всі дуги, по яким можна здійснити перехід з вузла х у вузол у, не змінюючи орієнтацію обходу, назвемо замиканням вузлів х і у, яке позначимо через w(х, у). Замикання w(х, у) є частковим замиканням в сітці, якщо х ¹ S, у ¹ t. У кожний момент часу для будь-яких двох вузлів множини К2 або К1 можна утворити тільки одне замикання, але таких замикань у сітці може бути стільки, скільки шляхів відмічено ознаками критичності. Кожне замикання однозначно визначено початковими і кінцевими вузлами.

Для побудови алгоритму розподілу ресурсів розглянемо попередньо задачу визначення оптимальної інтенсивності виконання робіт на замиканні. Розв’язання цієї задачі надалі буде складовою побудови календарного плану.

Користуючись наведеними позначеннями і визначеннями, розглянемо таку задачу.

Нехай на сітьовому графі визначені роботи, що складають критичний шлях. Відомі його довжина Ткр і найменша тривалість виконання кожної роботи (і, j) — tij. У кожний момент часу в сітці існує деякий фронт робіт. Тоді по критичній роботі (х*, у*) із фронта робіт можна побудувати замикання w(ху) (х = х* — початок замикання, у = у* — його кінець), в яке ввійдуть як дуги даного фронту, так і дуги наступних фронтів.

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

Ця задача зводиться до розв’язання задачі лінійного програмування в такій постановці.

Зафіксуємо множину шляхів П = {Пху} із х в у для замикання w(ху) і підрахуємо кількість шляхів у ньому за виключенням критичного шляху.

Розв’язуємо задачу визначення таких інтенсивностей hij обходу дуг замикання w(ху), за яких час фактичного обходу дуг замикання мінімально відрізнявся б від часу обходу дуг, що утворюють критичний шлях і потрапили в замикання, тобто необхідно шукати мінімум функції

, (6)

де — множина дуг критичного шляху.

З урахуванням (5) маємо

. (7)

Із умови, що тривалість tij обходу кожної дуги замикання обмежена знизу і зверху складом групи спеціалістів , отримуємо обмеження на змінні величини tij функції (7)

. (8)

Крім того, логічним є обмеження з фонду робочого часу jl кожного підрозділу за період

, l = 1, 2 … L . (9)

Аналогічно записується обмеження з фонду робочого часу підприємства в цілому за той самий період:

. (10)

Схема розв’язання задачі оптимізації розподілу ресурсів на замиканні сітки складається з таких етапів.

1. Шляхом розв’язання задачі лінійного програмування (7) —(10) визначають оптимальні значення для всіх (іj) Î w(ху).

2. Визначаються оптимальні значення величин hij за формулою

, (і, j) Î w(х, у). (11)

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

, (і, j) Î w(х, у). (12)

4. Здійснюється добір складу груп , що якнайкраще відповідають отриманим оцінкам, і їх закріплення за відповідними роботами (і, j) Î w(х, у).

5. Визначається період часу , протягом якого будуть виконані всі роботи, що належать w(х, у).

Література

Карагодова Е. А., Маслюк Г. Ф. Об одной задаче оптимального планирования на основе сетевых моделей с учетом ресурсов второго рода // Строительное производство. — 1968. — № 7. — К.: Будівельник. — С. 16—18.

І. Г. Лук’яненко, канд. екон. наук, доцент,
А. О. Губачов,
магістр Національний університет «Києво-Могилянська академія»

Добавить комментарий


Защитный код
Обновить