Общая задача теории расписаний

Обычно это задача календарного планирования, и ее варианты являются схемами основных задач по организации производства.

Имеется n станков и m деталей, каждая из которых должна пройти обработку на всех станках в определенной последовательности. Задано а _ij – время, необходимое для обработки j -ой детали на i -ом станке. Требуется найти такой порядок обработки деталей, который минимизировал бы общее время выполнения всех работ (длину производственного цикла). Несмотря на большое прикладное значение, пока получено решение только для случая двух станков. В этом случае, поскольку операции на первом станке можно выполнить без задержек, оптимизация заключается в минимизации суммарного времени простоя второго станка.

Примеры сведения практических задач к канонической транспортной задаче

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

Суммарный объем производства больше потребления - может быть введен фиктивный пункт потребления В_{n +1} с объемом потребления

b_{n +1 =} b_{n +1} – суммарный объем нереализованного продукта.

Размеры остатков в разных пунктах производства можно регулировать введением штрафа за единицу нереализованного продукта А _i.

Суммарный объем производства меньше потребления, то полное удовлетворение всех пунктов потребления невозможно. В этом случае необходимо организовать перевозки всего произведенного продукта так, чтобы наиболее важные пункты удовлетворялись полнее, и при этом суммарные транспортные расходы должны быть минимальны – вводится величина ущерба r _j при неудовлетворении пункта В _j.

Требуется минимизировать суммарные затраты

при условиях

, , x_ij > 0, y_j = b _j - , где

y_j – разность между потребностями пункта В _j и поставками в него.

Перевозки с резервированием.

В некоторых районах пунктов производства может возникнуть необходимость в резервировании определенного количества продукта.

I _к – совокупность номеров i -го пункта производства в к -ом районе.

Требуется организовать перевозки таким образом, чтобы в к -ом районе (к=1,…,s) сохранилось не менее V _к единиц продукта.

- V _к , .

Общее число продуктов, вывезенных из всех пунктов производства к -го района должно быть не менее, чем на V _к (величину заданного резерва) меньше суммарного количества продукта, произведенного в этом районе.

Задача сводится к задаче транспортного типа

При условиях

- удовлетворение спроса каждого пункта потребления;

из каждого пункта потребления не может быть вывезено продукта

больше, чем производится;

- V _к , - условие резервирования;

x_ij ≥ 0 , - объем перевозок неотрицательные числа (перевозки запрещены из пунктов потребления в пункты производства).

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

Ограничения на пропускные способности магистралей (в ограниченный промежуток времени) не позволят реализовать оптимальный план перевозок, полученный без учета этих ограничений.

В этом случае в транспортной задаче условие xij ≥ 0 , заменяется неравенством вида 0 ≤ хij ≤ dij, где dij – пропускная способность магистрали (ij), т.е. максимальный объем продукции, который может быть перевезен по этой магистрали за рассматриваемый промежуток времени. Такая задача может быть вообще неразрешимой (когда пропускная способность всех магистралей, ведущих к j-му потребителю меньше объема его потребностей).

Перевозки с промежуточной обработкой.

Задача может быть осложнена наличием промежуточных транспортных узлов, в которых производится обработка груза (перевалка на другой вид транспорта, доработка полуфабриката перед поступлением его в пункт потребления).

А₁,…, А_m – пункты производства с объемами производства а₁, …, а_m

В₁,…, В_n – пункты потребления с объемами потребления b₁,…, b_n

С₁,…, С_к – пункты промежуточной обработки.

Возможности пункта промежуточной обработки С_λ ограничены d _λ единицами продукта.

Стоимости перевозки единицы полуфабриката продукта из А_i в С_λ составляет С_iλ‘, стоимость перевозки единицы полуфабриката продукта из С_λ в В_j составляет С_λj“.

Составить такой план перевозок, при котором весь полуфабрикат вывозится, полностью обрабатывается, потребности всех пунктов потребления удовлетворяются и при этом транспортные расходы минимальны.

Математическая модель.

Z_iλj – количество продукта, доставляемое из пункта А _i в В_j через С _λ.

Транспортная таблица.

	B 1	B 2	…	B n	B n+1	B n+2	…	B n+k-1	B n+k
А 1	M	M		M	c’ 11	c’ 12		c’ 1,k-1	c’ 1k	a 1
А 2	M	M		M	c’ 21	c’ 21		c’ 2,k-1	c’ 2k	a 2
...				…						…
А m	M	M		M	c’ m1	c’ m2		c’ m?k-1	c’ mk	a m
А m+1	c” 11	c” 12		c” 1n		M		M	M	d 1
А m+2	c” 21	c” 21		c” 2n	M			M	M	d 2
…										…
А m+k-1	c” k-1,1	c” k-1,2		c” k-1,n	M	M	…		M	d k-1
А m+k	c” k1	c” k2		c” kn	M	M		M		d k
	b 1	B 2	…	B n	d 1	d 2	…	d k-1	d k

Определить план перевозок { Z _iλj}, на котором достигается минимум линейной формы

(С _iλ‘ + С _λj“) Z _iλj → min

при условиях

Z _iλj = а _i

Z _iλj = b _j

Z _iλj ≤ d _λ

Z _iλj ≥ 0, , ,

Необходимое и достаточное условие разрешимости задачи

а _i = b _j ≤ d _λ

Преобразуем, введя новые переменные

x _i,n+λ – количество полуфабриката, поступающее из пункта производства А _i в пункт обработки С _λ.

x _m+λ,j - количество полуфабриката, поступающее из пункта обработки С _λ в пункт потребления В_j.

x _i,n+λ = Z _iλj, , .

x _m+λ,j = Z _iλj, , .

В новых переменных задача формулируется так: требуется минимизировать

С _iλ‘ x _i,n+λ + С _λj“ x _m+λ,j

при условиях

x _i,n+λ = а _i, ,

x _m+λ,j = b _j ,

x _i,n+λ = x _m+λ,j ≤ d _λ

x _i,n+λ ≥ 0, x _m+λ,j ≥ 0, , , .

6.3 Распределительные задачи линейного программирования

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

Задачи распределения в общем виде можно разделить на два вида:

1. Задан объем работ. Имеются определенные ресурсы, т.е. фиксированные производственные мощности и количество материалов. Необходимо найти такой вариант использования ресурсов, который обеспечит минимальные затраты на выполнение заданных работ;

2. Заданы определенные материалы и оборудование (ресурсы). Необходимо определить, какая работа дает максимальную прибыль при использовании этих ресурсов.

Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи и прочие. Рассмотрим некоторые из них.