Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами




НазваниеМинимизация суммарного запаздывания выполнениЯ заданий параллельными приборами
страница1/11
Дата19.03.2013
Размер1.61 Mb.
ТипДокументы
  1   2   3   4   5   6   7   8   9   10   11

Глава 3Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами

Введение


Труднорешаемая задача комбинаторной оптимизации «Минимизация суммарного запаздывания при выполнении независимых заданий с равными весами и общим директивным сроком параллельными приборами» (МСЗП) формулируется следующим образом.

Задано множество заданий J, число приборов m, для каждого j  J известна длительность выполнения lj. Все задания имеют общий директивный срок d. Необходимо построить расписание  выполнения заданий j  J на m приборах одинаковой производительности такое, чтобы достигался минимум функционала:

F() = max [0; Cj() – d],

где Cj() — момент завершения выполнения задания j в последовательности .

Предполагается, что все задания множества J поступают одновременно, процесс обслуживания каждого задания можно начать в любой момент времени, он будет протекать без прерываний до завершения обслуживания задания.

Сформулированная задача относится к классу NP-трудных [0]. Она разрешима за псевдополиномиальное время при m = 2. Впервые эта задача рассматривалась нами в [0].

Указанная задача находит широкое применение при разработке систем планирования производства, управления проектами, управления строительством и в других областях. В частности, алгоритм решения задачи использован в иерархической модели планирования и управления сложными системами, имеющими сетевое представление технологических процессов и ограниченные ресурсы (глава 8).

В [0] получены следующие результаты. Пусть задания множества J = {1, 2,..., n} пронумерованы в порядке неубывания значений lj; Jk  J – множество заданий, обслуживаемых k-м прибором. Jk= {k, Rk}; ji  k, если Ci < d. В противном случае ji Rk.

Теорема 3.1 [0]. Существует оптимальное расписание, при котором

1) Ψ = {1, 2, …, |Ψ|},

2) если |Ψ| < n, то , и Rk содержит те и только те элементы R = {|Ψ|+1, …, n}, которые отличаются от |Ψ| + k на величину, кратную m, k = , где , а, если .

Пусть () – класс расписаний, удовлетворяющих условиям теоремы 3 .1 и дополнительным условиям: |Ψ| = , где  – натуральное число. Оптимальное расписание * принадлежит хотя бы одному из классов () при некотором  = *.

Теорема 3.2 [0]. Расписание () является оптимальным в (), если при этом расписании величина достигает наименьшего значения. Здесь: ; c() – число, равное остатку от деления (n – ) на m при n –  > 0 и равное m в противном случае.

Мы развиваем результаты, предложенные в [0], и предлагаем ПДС-алгоритм решения сформулированной задачи, обладающий такими свойствами: на основе теоретических свойств задачи МСЗП находятся логико-аналитические условия (p-условия), выполнение которых в процессе реализации заданной полиномиальной вычислительной схемой приводит к получению оптимального решения. Выполнение этих условий также служит критерием останова вычислений экпоненциональной составляющей ПДС-алгоритма.
  1   2   3   4   5   6   7   8   9   10   11

Похожие:

Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconСредний процент выполнения заданий репетиционного тестирования 2011
Результаты выполнения заданий по основным содержательным разделам учебного предмета «Русский язык»
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconМетодические рекомендации по оцениванию выполнения заданий егэ с развернутым ответом
Учебно-методические материалы для председателей и членов региональных предметных комиссий по проверке выполнения заданий с развернутым...
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconМетодические рекомендации по оцениванию выполнения заданий егэ с развернутым ответом Испанский язык
Учебно-методические материалы для председателей и членов региональных предметных комиссий по проверке выполнения заданий с развернутым...
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconМетодические рекомендации по оцениванию выполнения заданий егэ с развернутым ответом Немецкий язык (Раздел «Письмо»)
Учебно-методические материалы для председателей и членов региональных предметных комиссий по проверке выполнения заданий с развернутым...
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconМетодические рекомендации по оцениванию выполнения заданий егэ с развернутым ответом Английский язык
Учебно-методические материалы для председателей и членов региональных предметных комиссий по проверке выполнения заданий с развернутым...
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconМетодические рекомендации по оцениванию выполнения заданий егэ с развернутым ответом Французский язык (Раздел «Письмо»)
Учебно-методические материалы для председателей и членов региональных предметных комиссий по проверке выполнения заданий с развернутым...
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами icon1. Характеристика контрольных измерительных материалов единого государственного экзамена по физике в 2010 г
Экзаменационная работа по физике для егэ-2010 содержала 36 заданий: 25 заданий с выбором ответа (часть 1), 5 заданий с кратким ответом...
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconОтработать навык выполнения теста по данной теме. Материал расположен по принципу «От простого к сложному»: от повторения правила к отработке заданий, сформулированных для экзаменационного выполнения. Важно, что для заданий даны отве
С 2006 года в регионах Российской Федерации в рамках создания Общероссийской системы оценки качества образования проводится государственная...
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconЛабораторная работа №5 Анализ операций с ценными бумагами
Лабораторная работа №5 включает 5 заданий. Для выполнения этих заданий необходимо ознакомиться с теоретическим материалом, приведенным...
Минимизация суммарного запаздывания выполнениЯ заданий параллельными приборами iconИнструкция № по технике безопасности при работе электронагревательными приборами ( плита, мармит, жарочный шкаф, утюг, кипятильник и т п.)
К работе с электронагревательными приборами допускаются лица прошедшие инструктаж по правилам их безопасной эксплуатации
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница