Область наук:
  • Математика
  • Рік видавництва: 2004
    Журнал: Известия Південного федерального університету. Технічні науки

    Наукова стаття на тему 'Алгоритм розв'язання задачі побудови 2-процесорного розкладу'

    Текст наукової роботи на тему «Алгоритм розв'язання задачі побудови 2-процесорного розкладу»

    ?15. Системні дослідження: Щорічник, 1973.- М: Наука, 1974.- С. 52-62.

    16. Системний аналіз і наукове знання // Зб. Ін-ту філософії АН СРСР.- М .: Наука, 1978.- 247 с.

    17. Волкова В.М., Денисов А.А. Основи теорії систем і системного аналіза.- СПб .: Изд-во СПбДПУ, 2003.- 520 с.

    18. Згуровський М.З., Доброногов А.В., Померанцева Т.Н. Дослідження соціальних процесів на основі методології системного аналіза.- Київ: Наукова думка. 1997.- 190 с.

    19. Вінер Н. Кібернетіка.- М .: Сов. радіо, 1968.- 433 с.

    Л.І. Замкова, А.Г. Чефранов

    АЛГОРИТМ РІШЕННЯ ЗАВДАННЯ ПОБУДОВИ 2-процесорний розкладу

    1. Постановка завдання Завдання побудови 2-процесорного розкладу є КР-повній, тому існує можливість її рішення за псевдополіноміальное час. В роботі [1] пропонується використовувати метод вирішення задачі розбиття. Але завдання розбиття полиномиально зводиться до подзадаче завдання "2-процесорний розклад"

    1 2

    (Б = - | Е / г-). Тому цей метод не може бути використаний для вирішення загальної

    2 г = 1

    постановки завдання "2-процесорний розклад".

    Сформулюємо умову задачі побудови 2-процесорного розкладу. Визнач кінцеве пана елементне безліч А завдань, тривалості 1 ^ 2 кожного а, ЕА, число процесорів т = 2 і директивний термін В<е2. Чи існує розбиття А = А] ^ А2 безлічі А на т = 2 непересічних множин, таке що

    тах

    ,2

    2. Алгоритм рішення

    1. Якщо максимальна тривалість з I, | 1 = 1,2, ..., г більше Б, то розбиття не існує, вихід.

    2. Перевіряється умова /1+/2+...+4>2 * Б. Якщо умова вірна, то розбиття не існує, вихід.

    3. Методом функціональних рівнянь динамічного програмування вирішується завдання

    2

    Е 1г | У г ^ тах

    1 = 1

    2

    Е 1г | У г * Б (1)

    У; І0,1} г =

    2

    4. Якщо Е У г | I > Б, то розбиття не існує, вихід.

    г = 1

    5. Рішення у визначає безліч А ;, рішення у визначає безліч А2. Доведемо, що якщо у визначає максимальну вибірку з Ь, таку що

    22

    Е Уг • * Б, то при Е Уг 'Ь > Б розбиття не існує.

    г = 1 г = 1

    Известия ТРТУ

    Тематичний випуск

    Очевидно, виконується рівність

    2 2 + 2

    ЕУг | 1г + Еуг '1г = Е 1г

    г = 1 г = 1 г = 1 .

    = Б - до > Б

    2

    За побудовою алгоритму Е Уг | I вибирається максимально можливої ​​та-

    г = 1

    2

    кой, що Е Уг | Ь * Б. Отже, простий кг є мінімально можливим.

    г = 1

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

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

    Е УГ 1г + Е $ | 1г = Е 1г

    г = 1 г = 1 г = 1 '

    = Б - к2

    2

    де к2>к1. Але щоб рівність залишилося вірним, Е У | I має збільшитися з

    г = 1

    2 2 + 2

    порівняно з ЕУг '1г на к2-кг. Але величина ЕУг'Ь > Б і, отже, ЄУ 'Ь

    г = 1 г = 1 г = 1

    тим більше перевершує Б. Тобто, яку б перестановку ми не робили при вели-

    2

    чині Е У \ | I, менше або рівним Б, що залишилося безліч, яке визначається У, по

    г = 1

    сумі елементів буде більше Б. Тобто, розбиття не існує.

    Розроблений алгоритм, в основі якого лежать ідеї з роботи [2], базується на методі функціональних рівнянь динамічного програмування (МФУДП), який вирішує завдання про рюкзаку:

    2

    Е 1г | У г ^ тах

    г = 1 2

    Е Гг | У, * Б (2)

    У е1 °, 1} г = 1,2,-> 2

    Завдання (1) є окремим випадком завдання (2). Але в загальному випадку коефіцієнти в цільової функції не збігаються з коефіцієнтами в функції обмеження. Ідея МФУДП виражається формулою з роботи [3]:

    [Тах [4 (®), 4 + 1 + 4 (а - +1)], для а> гк + 1

    до + 1% (а) для а< гк + 1

    Процедура ітеріруется для кожного а й повторюється для? = 1,2, ..., р Підрахуємо кількість операцій, необхідне для знаходження оптимального вектора уг (Б). На одній ітерації:

    1) при а> Гк + 1 виконуються читання (а), віднімання а- Гк +1, читання

    Ьк (а - Гк + 1), підсумовування 1к + 1 + Ьк (а - гк + 1), знаходження максимуму

    тах ['к (а), 1к + 1 + Ьк (а - Гк + 1)] - 5 операцій;

    2

    2) при зі < Г? + І виконується читання (о) - 1 операція.

    Таким чином, складність МФУДП - 0 (х • Б).

    3. Висновок

    На основі алгоритму побудови 2-процесорного розкладу була розроблена програмна реалізація на мові Сі для ЕОМ ІВМ РС з процесором Су-гіх 486. Для Б = 40 і 2 = 20,40,60,80,100 час роботи програми відповідно 1,

    5, 12, 20, 25 секунд.

    В результаті вивчення предметної області не було виявлено ефективного способу вирішення завдання 2-процесорного розкладу в загальному формулюванні. У роботі пропонується псевдополіноміальний алгоритм вирішення поставленого завдання. Планується розвинути ідею, закладену в методі, для вирішення завдання "багатопроцесорне розклад". Автори повністю несуть відповідальність за результати.

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Гері М., Джонсон Д. Обчислювальні машини і труднорешаемие задачі.- М., 1982.-С. 124.

    2. Замкова Л.І., Чефранов А.Г. Тез. доп. Всерос. конф. з комп'ютерних технологій (19-21 червня 1996 р 21-23 жовтня 1997 р.) .- Таганрог, ТРТУ, 1998.- С. 88-90.

    3. Данциг Дж. Лінійне програмування його узагальнення і прімененія.- М., 1966.-С. 490-491.

    І.М. Калякина ДИНАМІЧНІ факторну модель аналізу діяльності МАЛИХ ПІДПРИЄМСТВ

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

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

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

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


    Завантажити оригінал статті:

    Завантажити