Модели расписаний работы каскада экстракторов с учетом стадии подготовки многоассортиментного сырья
УДК 641.524.6:664.5
Модели расписаний работы каскада экстракторов с учетом стадии подготовки многоассортиментного
сырья.
Перов А.Г., Косачев В.С., д.т.н. Кошевой Е.П.
Кубанский государственный технологический университет
Представленный оптимальный порядок переработки сырья позволит провести стадию дробления с минимальными потерями связанных средств. Такой порядок переработки партий сырья может быть использован для определения порядка использования группы экстракторов при переходе группы установок с одного сырья на другое.
Ключевые слова: экстракция, теория расписаний, эфиромасличном сырье.
Для оптимизации расписания группы установок с учетом стадии подготовки сырья рассмотрим эту стадию при переработке многоассортиментного потока сырья. В этом случае используем модель переработки множества партий на одной операции с разной длительностью. В теории расписаний есть ряд задач, которые имеют большое практическое значение и сравнительно просто решаются. К их числу может быть отнесена задача с одним обслуживающим устройством. Дадим постановку этой задачи в терминах «машина—работа (операция)». Здесь термины «работа» и «операция» обозначают фактически одно и то же, поскольку каждая работа состоит из одной операции. Эта терминология будет использована и в дальнейшем.
Пусть для выполнения на одной машине одновременно поступает множество N={1, 2, ..., N} работ (случай, когда работы поступают не одновременно, а в некоторые фиксированные моменты времени, может быть легко сведен к рассматриваемому). Также предположим, что продолжительность выполнения каждой работы на машине известна, и обозначим ее через ti, i∈N. Задача построения расписания для выполнения множества работ одной машиной состоит в том, чтобы определить такой порядок выполнения работ, при котором некоторый заданный критерий эффективности будет принимать оптимальное значение. Критерий завершения всех работ не эффективен, так как не зависит от перестановки перерабатываемых партий сырья.
Метод решения задачи существенно зависит от критерия эффективности. Прежде чем сформулировать различные критерии эффективности, которые используются для оценки качества расписаний, введем следующие обозначения, необходимые в дальнейшем: t′i — время
начала выполнения работы i∈N; t′′i — время окончания выполнения работы
i∈N; di — директивное время, в течение которого должно быть завершено выполнение работы i∈N; αi — штраф за ожидание работы i в единицу времени (или некоторая стоимость, связанная с выполняемой работой) до
момента начала ее обработки i∈N; βi — стоимость выполнения работы i, i∈N. Время начала и окончания выполнения работ связано следующей
зависимостью:
ti′′ = ti′ + ti
(1)
Здесь и в дальнейшем предполагается, что перерывы в выполнении
работ не допускаются. Это значит, что если машина приступила к
выполнению некоторой работы, то она продолжает выполнять ее до тех пор,
пока не закончит. Время T, необходимое для выполнения всех работ
множества N, не зависит от порядка выполнения работ и равно сумме времен
выполнения всех работ:
∑T = ti . i∈N
(2)
Учитывая принятые обозначения, можно записать, что задержка zi
(превышение директивного срока пребывания в системе) работы i составит:
zi
=
max(0, i∈N
t
i′′
−
d
i
),
i
∈
N
.
(3)
Таким образом, критерий эффективности, определяющий величину
суммарных издержек, связанных с опозданием в выполнении работ к
заданным срокам, будет иметь вид:
∑Φ1 = αi ⋅ zi
i∈N .
(4)
Критерий, позволяющий вычислять максимальный штраф, связанный
также с опозданием в выполнении работ, имеет вид
( )Φ2
=
max i∈N
αi
⋅ zi
.
(5)
Этот критерий приводит к построению такого расписания, в котором
издержки, связанные с опозданием в выполнении работ, распределены
наиболее равномерно. При решении различных задач критерии (4) и (5), как
правило, требуется обратить в минимум. Часто встречается критерий:
∑Φ3 = αi ⋅ ti′
i∈N .
(6)
Представляющий сумму штрафов, связанных с ожиданием работ в
системе, которую необходимо минимизировать.
Рассмотрим задачу минимизации суммы связанных средств на
производственном участке. Стоимость, связанная с выполняемой работой,
после ее выполнения будет равна γi=αi+βi. Время, в течение которого выполненная работа i будет находиться на участке, ожидая окончания
выполнения всех работ, составит T−t′′i. Общее количество связанных
денежных средств:
F = ∑γ i ⋅ (T − ti′′)
(7)
i∈N .
Подставляя в (7) выражение завершения работ (1), раскрывая скобки и
вынося неиндексированные переменные за знак суммы имеем:
F = T ⋅ ∑γ i − ∑γ i ⋅ti ' + ∑(− γ i )⋅ti
i∈N i∈N
i∈N
.
(8)
Так как первое и последнее слагаемое (8) постоянны и не зависят от
порядка выполнения работ, на основании выражения (8) может быть записан
критерий:
∑Φ4 = (− γ i )⋅ti '
i∈N .
(9)
Который можно использовать для минимизации суммы связанных
средств. Нетрудно заметить аналогию между критериями (6) и (9) поэтому
правило, минимизирующее Ф3, можно использовать и для построения расписания, оптимального по критерию Ф4. Учитывая наличие летучих целевых компонентов в перерабатываемом сырье наиболее важны критерии
Ф3, Ф4. Учитывая их взаимосвязь, рассмотрим задачу построения оптимального расписания по критерию Ф3. Для вывода правила воспользуемся следующими рассуждениями: пусть имеется оптимальное
расписание, в котором номера выполняемых работ совпадают с порядковыми
номерами работ. Тогда этому расписанию будет соответствовать
минимальное значение критерия (6). Всякая перестановка в порядке
выполнения двух или более работ уже не может привести к уменьшению
этого критерия эффективности, поэтому переставив местами работы с
номерами k и k + 1, можно записать, что Ф3opt ≤ Ф3’, где Ф3opt, Ф3’ — соответственно минимальное значение критерия эффективности полученное
до и после осуществления перестановки.
Тогда с учетом критерия (6) данное неравенство может быть записано в
виде:
k−1 n
∑ ∑αi ⋅ ti′ + αk ⋅ tk′ + αk+1 ⋅ tk′+1 + αi ⋅ ti′ ≤
i=1 i=k+2
k−1 n
∑ ∑≤ αi ⋅ t'i + αk+1 ⋅ t′k+1 + αk ⋅ t′k + αi ⋅ t'i
i=1
i=k+2
,
(10)
где t′k, t′k+1 — время начала выполнения соответственно k-й и (k-1)-й работы после перестановки. Заметим, что как в первом (в оптимальном), так и во
втором (с перестановкой) расписании k-я и (k-1)-я работы начнут
выполняться после того, как будут выполнены предшествующие k-1 работы,
поэтому t′k= t′k+1, а t′k+1= t′k+ tk. Кроме того t′k = t′k+1 + tk+1. Из этого следует
t′k = t′k + tk+1. В результате можно записать:
( ) ( )αk ⋅ tk′ + αk+1 ⋅ tk′ + tk ≤ αk+1 ⋅ tk′ + αk ⋅ tk′ + tk+1 .
(11)
Выполнив простейшие преобразования, получим:
α k+1 ⋅ tk ≤ α k ⋅ tk+1 ,
(12)
откуда:
tk ≤ tk+1 α k α k+1 .
(13)
На основании этого соотношения может быть сформулировано
следующее правило построения оптимального по критерию (6) расписания:
Для всех работ вычислить отношение ti/αi; Упорядочить работы по возрастанию этого отношения.
Воспользовавшись выражением (13) получим правило для построения
расписания, минимизирующего сумму связанных средств, которое имеет
следующий вид:
tk ≥ tk+1 γ k γ k+1 .
(14)
Это значит, что работы должны быть упорядочены в порядке убывания
отношения ti/γi. Учитывая взаимосвязь критериев (5) и (6) приведем алгоритм построения оптимального расписания по критерию (5).
Предварительный шаг. Вычисляем время окончания выполнения всех
работ T и переходим к первому шагу.
Первый шаг. Среди всех неупорядоченных работ находим такую (l), для
которой:
αL
⋅
zL
=
min(α i
i
⋅
zi ) ,
(15)
где zi = max(0, T-di);
min i
— вычисляется по множеству индексов только
неупорядоченных работ.
Второй шаг. Работу с номером l выполняем последней среди
рассматриваемого множества. Исключаем работу l из рассмотрения. Если
множество работ пусто, то задача решена. Если нет, то заменяем T на T−ti и переходим к первому шагу.
После повторения N раз первого и второго шагов будет построено
расписание, оптимальное по критерию (5).для построения расписаний,
оптимальных по критерию (4), нет таких простых, упорядочивающих
расписание, правил. Поэтому используем метод полного перебора.
Учитывая наличие легко летучих компонентов в перерабатываемом
эфиромасличном сырье значение параметров αi и βi можно принять пропорциональными массе извлекаемого продукта и времени дробления
партии этого сырья (соответственно). Рассмотрим задачу упорядочивания по представленным критериям наиболее типичного производственного набора (таблица 1).
Таблица 1 Параметры производственного процесса по каждому виду сырья.
Наименования сырья
Кориандр Гвоздика
Укроп
Хмель
Вес продукта, кг
0,525
5,2
0,84 0,3
Дробление, мин.
10
20
15
25
Цена продукта, руб./кг
3017
2220
3173
3444
Σ, руб.
1584
11544
2665
1033
Представленные данные позволяют определить оптимальный порядок переработки сырья по критериям максимальных потерь (5) и суммы потерь (6) по представленным алгоритмам. Для этого по правилу (13) вычислим отношение ti/αi и пронумеруем партии в порядке их возрастания (таблица 2).
Таблица 2 Оптимальный порядок переработки партий минимизирующий
сумму потерь продукта.
Параметры
Кориандр
Вид сырья Укроп Гвоздика
Хмель
Критерий
0,063
0,084
0,035
0,605
Оптимальный порядок
3412
Выводы:
Представленный оптимальный порядок переработки сырья позволит провести стадию дробления с минимальными потерями связанных средств. Такой порядок переработки партий сырья может быть использован для определения порядка использования группы экстракторов при переходе группы установок с одного сырья на другое.
Список литературы
1. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. 322 с.
2. Кафаров, В.В., Мешалкин В.П. - Анализ и синтез химико-технологических систем. М.: Химия, 1991. — 431 с.
3. Колчин А.Ф., Овсянников М.В., Стрекалов А.Ф., Сумароков С.В. Управление жизненным циклом продукции. — М. : Анахарсис, 2002. — 304 с.
4. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М., Наука, 1975 г.
Модели расписаний работы каскада экстракторов с учетом стадии подготовки многоассортиментного
сырья.
Перов А.Г., Косачев В.С., д.т.н. Кошевой Е.П.
Кубанский государственный технологический университет
Представленный оптимальный порядок переработки сырья позволит провести стадию дробления с минимальными потерями связанных средств. Такой порядок переработки партий сырья может быть использован для определения порядка использования группы экстракторов при переходе группы установок с одного сырья на другое.
Ключевые слова: экстракция, теория расписаний, эфиромасличном сырье.
Для оптимизации расписания группы установок с учетом стадии подготовки сырья рассмотрим эту стадию при переработке многоассортиментного потока сырья. В этом случае используем модель переработки множества партий на одной операции с разной длительностью. В теории расписаний есть ряд задач, которые имеют большое практическое значение и сравнительно просто решаются. К их числу может быть отнесена задача с одним обслуживающим устройством. Дадим постановку этой задачи в терминах «машина—работа (операция)». Здесь термины «работа» и «операция» обозначают фактически одно и то же, поскольку каждая работа состоит из одной операции. Эта терминология будет использована и в дальнейшем.
Пусть для выполнения на одной машине одновременно поступает множество N={1, 2, ..., N} работ (случай, когда работы поступают не одновременно, а в некоторые фиксированные моменты времени, может быть легко сведен к рассматриваемому). Также предположим, что продолжительность выполнения каждой работы на машине известна, и обозначим ее через ti, i∈N. Задача построения расписания для выполнения множества работ одной машиной состоит в том, чтобы определить такой порядок выполнения работ, при котором некоторый заданный критерий эффективности будет принимать оптимальное значение. Критерий завершения всех работ не эффективен, так как не зависит от перестановки перерабатываемых партий сырья.
Метод решения задачи существенно зависит от критерия эффективности. Прежде чем сформулировать различные критерии эффективности, которые используются для оценки качества расписаний, введем следующие обозначения, необходимые в дальнейшем: t′i — время
начала выполнения работы i∈N; t′′i — время окончания выполнения работы
i∈N; di — директивное время, в течение которого должно быть завершено выполнение работы i∈N; αi — штраф за ожидание работы i в единицу времени (или некоторая стоимость, связанная с выполняемой работой) до
момента начала ее обработки i∈N; βi — стоимость выполнения работы i, i∈N. Время начала и окончания выполнения работ связано следующей
зависимостью:
ti′′ = ti′ + ti
(1)
Здесь и в дальнейшем предполагается, что перерывы в выполнении
работ не допускаются. Это значит, что если машина приступила к
выполнению некоторой работы, то она продолжает выполнять ее до тех пор,
пока не закончит. Время T, необходимое для выполнения всех работ
множества N, не зависит от порядка выполнения работ и равно сумме времен
выполнения всех работ:
∑T = ti . i∈N
(2)
Учитывая принятые обозначения, можно записать, что задержка zi
(превышение директивного срока пребывания в системе) работы i составит:
zi
=
max(0, i∈N
t
i′′
−
d
i
),
i
∈
N
.
(3)
Таким образом, критерий эффективности, определяющий величину
суммарных издержек, связанных с опозданием в выполнении работ к
заданным срокам, будет иметь вид:
∑Φ1 = αi ⋅ zi
i∈N .
(4)
Критерий, позволяющий вычислять максимальный штраф, связанный
также с опозданием в выполнении работ, имеет вид
( )Φ2
=
max i∈N
αi
⋅ zi
.
(5)
Этот критерий приводит к построению такого расписания, в котором
издержки, связанные с опозданием в выполнении работ, распределены
наиболее равномерно. При решении различных задач критерии (4) и (5), как
правило, требуется обратить в минимум. Часто встречается критерий:
∑Φ3 = αi ⋅ ti′
i∈N .
(6)
Представляющий сумму штрафов, связанных с ожиданием работ в
системе, которую необходимо минимизировать.
Рассмотрим задачу минимизации суммы связанных средств на
производственном участке. Стоимость, связанная с выполняемой работой,
после ее выполнения будет равна γi=αi+βi. Время, в течение которого выполненная работа i будет находиться на участке, ожидая окончания
выполнения всех работ, составит T−t′′i. Общее количество связанных
денежных средств:
F = ∑γ i ⋅ (T − ti′′)
(7)
i∈N .
Подставляя в (7) выражение завершения работ (1), раскрывая скобки и
вынося неиндексированные переменные за знак суммы имеем:
F = T ⋅ ∑γ i − ∑γ i ⋅ti ' + ∑(− γ i )⋅ti
i∈N i∈N
i∈N
.
(8)
Так как первое и последнее слагаемое (8) постоянны и не зависят от
порядка выполнения работ, на основании выражения (8) может быть записан
критерий:
∑Φ4 = (− γ i )⋅ti '
i∈N .
(9)
Который можно использовать для минимизации суммы связанных
средств. Нетрудно заметить аналогию между критериями (6) и (9) поэтому
правило, минимизирующее Ф3, можно использовать и для построения расписания, оптимального по критерию Ф4. Учитывая наличие летучих целевых компонентов в перерабатываемом сырье наиболее важны критерии
Ф3, Ф4. Учитывая их взаимосвязь, рассмотрим задачу построения оптимального расписания по критерию Ф3. Для вывода правила воспользуемся следующими рассуждениями: пусть имеется оптимальное
расписание, в котором номера выполняемых работ совпадают с порядковыми
номерами работ. Тогда этому расписанию будет соответствовать
минимальное значение критерия (6). Всякая перестановка в порядке
выполнения двух или более работ уже не может привести к уменьшению
этого критерия эффективности, поэтому переставив местами работы с
номерами k и k + 1, можно записать, что Ф3opt ≤ Ф3’, где Ф3opt, Ф3’ — соответственно минимальное значение критерия эффективности полученное
до и после осуществления перестановки.
Тогда с учетом критерия (6) данное неравенство может быть записано в
виде:
k−1 n
∑ ∑αi ⋅ ti′ + αk ⋅ tk′ + αk+1 ⋅ tk′+1 + αi ⋅ ti′ ≤
i=1 i=k+2
k−1 n
∑ ∑≤ αi ⋅ t'i + αk+1 ⋅ t′k+1 + αk ⋅ t′k + αi ⋅ t'i
i=1
i=k+2
,
(10)
где t′k, t′k+1 — время начала выполнения соответственно k-й и (k-1)-й работы после перестановки. Заметим, что как в первом (в оптимальном), так и во
втором (с перестановкой) расписании k-я и (k-1)-я работы начнут
выполняться после того, как будут выполнены предшествующие k-1 работы,
поэтому t′k= t′k+1, а t′k+1= t′k+ tk. Кроме того t′k = t′k+1 + tk+1. Из этого следует
t′k = t′k + tk+1. В результате можно записать:
( ) ( )αk ⋅ tk′ + αk+1 ⋅ tk′ + tk ≤ αk+1 ⋅ tk′ + αk ⋅ tk′ + tk+1 .
(11)
Выполнив простейшие преобразования, получим:
α k+1 ⋅ tk ≤ α k ⋅ tk+1 ,
(12)
откуда:
tk ≤ tk+1 α k α k+1 .
(13)
На основании этого соотношения может быть сформулировано
следующее правило построения оптимального по критерию (6) расписания:
Для всех работ вычислить отношение ti/αi; Упорядочить работы по возрастанию этого отношения.
Воспользовавшись выражением (13) получим правило для построения
расписания, минимизирующего сумму связанных средств, которое имеет
следующий вид:
tk ≥ tk+1 γ k γ k+1 .
(14)
Это значит, что работы должны быть упорядочены в порядке убывания
отношения ti/γi. Учитывая взаимосвязь критериев (5) и (6) приведем алгоритм построения оптимального расписания по критерию (5).
Предварительный шаг. Вычисляем время окончания выполнения всех
работ T и переходим к первому шагу.
Первый шаг. Среди всех неупорядоченных работ находим такую (l), для
которой:
αL
⋅
zL
=
min(α i
i
⋅
zi ) ,
(15)
где zi = max(0, T-di);
min i
— вычисляется по множеству индексов только
неупорядоченных работ.
Второй шаг. Работу с номером l выполняем последней среди
рассматриваемого множества. Исключаем работу l из рассмотрения. Если
множество работ пусто, то задача решена. Если нет, то заменяем T на T−ti и переходим к первому шагу.
После повторения N раз первого и второго шагов будет построено
расписание, оптимальное по критерию (5).для построения расписаний,
оптимальных по критерию (4), нет таких простых, упорядочивающих
расписание, правил. Поэтому используем метод полного перебора.
Учитывая наличие легко летучих компонентов в перерабатываемом
эфиромасличном сырье значение параметров αi и βi можно принять пропорциональными массе извлекаемого продукта и времени дробления
партии этого сырья (соответственно). Рассмотрим задачу упорядочивания по представленным критериям наиболее типичного производственного набора (таблица 1).
Таблица 1 Параметры производственного процесса по каждому виду сырья.
Наименования сырья
Кориандр Гвоздика
Укроп
Хмель
Вес продукта, кг
0,525
5,2
0,84 0,3
Дробление, мин.
10
20
15
25
Цена продукта, руб./кг
3017
2220
3173
3444
Σ, руб.
1584
11544
2665
1033
Представленные данные позволяют определить оптимальный порядок переработки сырья по критериям максимальных потерь (5) и суммы потерь (6) по представленным алгоритмам. Для этого по правилу (13) вычислим отношение ti/αi и пронумеруем партии в порядке их возрастания (таблица 2).
Таблица 2 Оптимальный порядок переработки партий минимизирующий
сумму потерь продукта.
Параметры
Кориандр
Вид сырья Укроп Гвоздика
Хмель
Критерий
0,063
0,084
0,035
0,605
Оптимальный порядок
3412
Выводы:
Представленный оптимальный порядок переработки сырья позволит провести стадию дробления с минимальными потерями связанных средств. Такой порядок переработки партий сырья может быть использован для определения порядка использования группы экстракторов при переходе группы установок с одного сырья на другое.
Список литературы
1. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. 322 с.
2. Кафаров, В.В., Мешалкин В.П. - Анализ и синтез химико-технологических систем. М.: Химия, 1991. — 431 с.
3. Колчин А.Ф., Овсянников М.В., Стрекалов А.Ф., Сумароков С.В. Управление жизненным циклом продукции. — М. : Анахарсис, 2002. — 304 с.
4. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М., Наука, 1975 г.