Свойства допустимых и оптимальных маршрутов приема и доставки грузов

Допустимые маршруты движения транспортных средств

Пусть определены подмножества /,,/2, выполнения

заданий для каждой к-й машины, где /А — Jk {/* ,ik,...JkN} . Начало выполнения всех маршрутов допустимо в момент времени в = О. Рассмотрим последовательность выполнения этих заданий в порядке не возрастания граничных времён их завершения -

Пусть Nk - количество заданий, выполняемых на к-и машине. Справедливы следующие утверждения:

Утверждение 5.1. Если не выполняется хотя бы одно из неравенств системы

где = tk + min min ak ? > a " количество объектов, обслужи-

"jf j< l'i‘

ваемых к -й машиной, и это обслуживание осуществляется в последовательности (5.9),

то не существует допустимых расписаний выполнения данного комплекса работ Jк на к -й машине.

Доказательство аналогичного утверждения перестановочным приемом и методом индукции приведено, например, в [2, 10,37, 38], и в работах автора [29, 33].

Следствие утверждения 5.1. Если все элементы матриц Ак, к = 1 , равны 0, т.е. akj =0, i,j =, то, если не выполняется хотя бы одно из неравенств системы

то не существует допустимых расписаний выполнения данного комплекса работ Jk на к -й машине.

Пусть для каждого из обслуживаемых пунктов установлены dt - наиболее ранние сроки начала приема или доставки грузов, а также заданы вк - допустимое время начала работы к -й машины. Утверждение 5.2. Если не выполняется хотя бы одно из неравенств системы

то не существует допустимых расписаний выполнения данного комплекса работ на к -й машине.

Следствие утверждения 5.2. Если ак =0, =

к = 1,..., К , то система неравенств (5.12) имеет вид

Предположим, что необходимо построить оптимальное расписание по критерию Fmax , т.е. определены

подмножества заданий, выполняемых на каждой машине.

/l,/2, ••••Л к? "-ч* к »

  • - для всех заданий справедливы условия: бГ = 0, /) = со, / = 1,..., N , а также отсутствуют ограничения на частичные порядки выполнения заданий;
  • - для всех машин вк = 0, Нк = оо, к = 1,..., К .

Утверждение 5.3. Оптимальное решение в этих условиях достигается, если выполнение всех задания на каждой машине осуществляется в последовательности

Доказательство утверждения следует из следующих заключений. Справедливость утверждения для случая одной машины перестановочным приемом и методом индукции впервые было получено Э. Лившицем и приведено во многих публикациях (см., например, [10]). Минимальное значение суммы достигася при минимальном значении каждого из его слагаемых.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >