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


Глава 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) Ψ = Ψ,
2) если |Ψ| < n, то , и Rk содержит те и только те элементы R = Ψ, которые отличаются от |Ψ| + k на величину, кратную m, k = , где , а, если .
Пусть () – класс расписаний, удовлетворяющих условиям теоремы 3 .1 и дополнительным условиям: |Ψ| = , где  – натуральное число. Оптимальное расписание * принадлежит хотя бы одному из классов () при некотором  = *.
Теорема 3.2 [0]. Расписание () является оптимальным в (), если при этом расписании величина достигает наименьшего значения. Здесь: ; c() – число, равное остатку от деления (n – ) на m при n –  > 0 и равное m в противном случае.
Мы развиваем результаты, предложенные в [0], и предлагаем ПДС-алгоритм решения сформулированной задачи, обладающий такими свойствами: на основе теоретических свойств задачи МСЗП находятся логико-аналитические условия (p-условия), выполнение которых в процессе реализации заданной полиномиальной вычислительной схемой приводит к получению оптимального решения. Выполнение этих условий также служит критерием останова вычислений экпоненциональной составляющей ПДС-алгоритма.

razdel-2-organizaciya-rezhima-prebivaniya-detej-v-obrazovatelnom-uchrezhdenii.html
razdel-2-organizaciya-samostoyatelnoj-uchebnoe-posobie-ministerstvo-obrazovaniya-i-nauki-rossijskoj-federacii-federalnoe.html
razdel-2-organizaciya-sorevnovanij-pravila-vida-sporta-sport-slepih-obshie-polozheniya-vid-sporta-sport-slepih.html
razdel-2-osnovi-hudozhestvennogo-izobrazheniya-poyasnitelnaya-zapiska-3-svodnaya-tablica-razdelov-i-raspredelenie-uchebnoj.html
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат
Реферат