Элементарные задачи упорядочения решались с помощью графиков, подобных графикам Ганта. Аналитические методы решения подобных задач разработаны главным образом для несложных типовых случаев.
Для большинства задач упорядочения решение приходится искать с помощью метода моделирования или через эвристические алгоритмы построения решения.
Ситуация 1. Рассмотрим элементарную практическую ситуацию. В водохранилище перед шлюзом стоят три судна. Их подготовка и проводка через шлюз требуют 8, 10 и 27 часов соответственно. Требуется выбрать очередность проводки судов, обеспечивающую минимальную сумму времени ожидания. Если, например, первым пойдет второе судно, то два оставшихся будут ожидать 10 часов.
Несложно придти к выводу, что предпочтительная очередность соответствует проводке судов в порядке повышения индивидуальных затрат времени. «Меньшее время обработки ставится на первое место».
Ситуация 2. Рассмотрим подобную ситуацию с тремя судами при условии, что подготовка и проводка требуют одинакового времени, но плата за простой для судов составляет 1, 5 и 9 руб. в час соответственно. Требуется выбрать очередность проводки судов, обеспечивающую минимум суммы выплат за простой судов.
Предпочтительная очередность соответствует проводке судов в порядке уменьшения цены за простой. «Большая цена за ожидание ставится на первое место».
Ситуация 3. Рассмотрим практическую ситуацию, объединяющую первые две. В водохранилище перед шлюзом стоят три судна. Их подготовка и проводка через шлюз требуют 8, 10 и 27 часов соответственно. Плата за их простой равняется 1, 5 и 9 руб. в час соответственно. Требуется выбрать очередность проводки судов, обеспечивающую минимум суммы оплаты за их простой.
На выбор очередности проводки судов влияют два параметра, причем действующие в противоположных направлениях. Правило приоритета очередности в этом случае базируется на отношении время/цена. Деление на цену простоя фактически приводит к одинаковой ценности времени и сводит третью ситуацию по «времени проводки» к первой, откуда следует правило очередности. «Меньшее время проводки ставится на первое место».
Математическая постановка задачи Совокупность деталей (работ) (/) характеризуется t (i) – временем обработки (выполнения), с() – платой за единицу времени простоя (ожидания).
Для первой ситуации, в которой предполагается равенство цены простоя, оценка имеет следующий вид:
J = T(1) + T(2) +… + T(i) → min,
где T (i) – время ожидания детали, поставленной на i – е место.
Правило выбора очередности обработки деталей (выполнения работ) должно приводить к условию
t(1) < t(2) < t(3)…
«Деталь с меньшим временем обработки проходит в первую очередь». Для второй ситуации оценка имеет вид
J = T(1) c(1) + T(2) c(2) + … → min.
Правило выбора очередности обработки деталей должно приводить к условию
с(1) > c(2) > c(3) …
«Деталь с большей ценой пролеживания обрабатывается в первую очередь». Для третьей ситуации оценка имеет вид
J = T(1) c(1) + T(2) c(2) + … → min.
Правило выбора очередности обработки деталей должно приводить к условию?
«Деталь с меньшим приведенным временем пролеживания обрабатывается в первую очередь».
