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

Интеллектуальное управление и автоматизация
Vol. 3 № 4 (2012) , Статья ID: 24892 , 6 страниц DOI:10.4236/ica.2012.34045 Функция вознаграждения для решения проблемы замены

Eva Selene Hernández Gress. Oscar Montaño Arango. José Ramón Corona Armenta. Antonio Oswaldo Ortega Reyes

Академическая область инженерии. Автономный университет Идальго. Пачука, Мексика

Электронная почта: evah@uaeh.edu.mx

Получено 5 мая 2012 года; пересмотрено 22 августа 2012 года; принято 30 августа 2012 года

Ключевые Слова: Цепи Маркова; Динамическое Программирование; Задача Замены

АБСТРАКТНЫЙ

Задача замены может быть смоделирована как конечная. Неприводимая. Однородная Марковская цепь. В нашем предложении задача была смоделирована с использованием марковского процесса принятия решений. А затем экземпляр был оптимизирован с помощью динамического программирования. Мы предложили новый функционал. Который включает в себя функционал вознаграждения. Который может быть более полезен в обрабатывающих отраслях. Поскольку он учитывает такие моменты. Как доходы. Затраты на техническое обслуживание. Постоянные затраты на замену оборудования. Покупную цену и стоимость утилизации; и этот функционал может быть решен с помощью динамического программирования и использован для принятия эффективных решений.

Доказаны две теоремы. Связанные с этим новым функционалом. Численный пример представлен для того. Чтобы продемонстрировать полезность этого предложения.

1. введение

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

Элементы. Которые находятся в постоянном использовании. Нуждаются в замене в соответствующее время. Поскольку эффективность операционной системы. Которая использует такие элементы. Сильно страдает. В этом предложении мы включаем функцию вознаграждения. Которая более полезна в обрабатывающих отраслях. Потому что она учитывает такие моменты. Как доходы. Расходы на техническое обслуживание. Постоянные затраты на замену оборудования. Покупную цену и стоимость утилизации;

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

В реальном мире проблема замены оборудования заключается в выборе двух или более машин одного или нескольких типов из набора нескольких возможных альтернативных машин с различной производительностью. Стоимостью покупки и эксплуатацией для эффективного производства. Когда речь идет об одной машине. Обычно встречаются две четко определенные формы этой замены: замена. Основанная на количестве, и замена. Основанная на времени. В модели замещения. Основанной на количестве. Машина заменяется. Когда производится накопленный продукт размера q.

В этой модели необходимо определить оптимальный размер производства q. В то время как в модели замещения. Основанной на времени. Машина заменяется в каждом периоде T с максимизацией прибыли.

Когда проблема затрагивает две или более машин. Эта проблема называется проблемой параллельной замены машин. А основанная на времени модель замены состоит в нахождении политики замены с минимальными затратами для конечной совокупности экономически взаимозависимых машин.

Политика замены-это спецификация действий “сохранить” или “заменить”. По одному для каждого периода.

Два простых примера-это политика замены оборудования каждый период времени и политика сохранения первой машины до конца периода N. Оптимальная политика-это политика. Которая обеспечивает наименьшую общую чистую стоимость владения на всем горизонте планирования. И она обладает тем свойством. Что независимо от исходного состояния и первоначального решения остальные решения должны составлять оптимальную политику в отношении состояния. Вытекающего из первого решения. На практике проблема замены может быть легко решена с помощью динамического программирования и марковских процессов принятия решений.

Динамическое программирование использует следующую идею: система наблюдается над конечным или бесконечным горизонтом. Разделенным на периоды или этапы. На каждом этапе система соблюдается. И решение или действие в отношении системы должно быть принято. Решение влияет (детерминистически или стохастически) на состояние. Которое будет наблюдаться на следующем этапе. И в зависимости от состояния и принятого решения достигается немедленное вознаграждение. Ожидаемое общее вознаграждение на данном этапе и одно из следующих состояний выражается функциональным уравнением.

Оптимальные решения в зависимости от стадии и состояния определяются в обратном порядке шаг за шагом как максимизирующие правую часть функционального уравнения [1]. Говард [2] сочетает технику динамического программирования с математически хорошо устоявшимся понятием цепи Маркова. Создавая новую концепцию. Называемую процессами принятия решений Маркова. И развивая решение задач с бесконечными стадиями. Метод итерации политики был создан как альтернатива шаговым обратным методам сжатия. Итерация политики была результатом применения среды цепи Маркова и внесла важный вклад в развитие методов оптимизации [

1].

В этом документе рассматривается стохастическая модель замены машины. Система состоит из одной машины. И предполагается. Что она работает непрерывно и эффективно в течение N периодов. В каждом периоде качество машины ухудшается из-за ее использования. И поэтому она может находиться в любом из N состояний. Обозначаемых 1, 2,···. N. В нашем предложении мы смоделировали задачу с помощью марковского процесса принятия решений. А затем экземпляр оптимизировали с помощью динамического программирования. Мы предлагаем новый функционал. Который включает в себя функцию вознаграждения. А также полезную информацию. Такую как доходы. Расходы на техническое обслуживание. Постоянные затраты на замену оборудования. Покупная цена и стоимость утилизации.

Доказаны две теоремы. Связанные с этим новым функционалом.

В этом предложении предполагается. Что для каждой новой машины ее состояние может ухудшаться или может оставаться неизменным. И что вероятности перехода pij известны, где

также предполагается. Что состояние машины известно в начале каждого периода. И мы должны выбрать один из следующих двух вариантов: а) Пусть машина работает еще один период в том состоянии. В котором она находится в настоящее время. Б) Заменить машину новой. Где все новые машины для замены считаются идентичными.

2. Обзор литературы

Существует несколько теоретических моделей для определения оптимальной политики замещения. Базовая модель учитывает затраты на техническое обслуживание и стоимость перепродажи. Которые имеют свое стандартное поведение в соответствии с той же стоимостью в более ранний период. А также частично имеют экспоненциальный рост с течением времени. Аналогично, можно считать. Что стоимость лома для используемого изделия имеет аналогичный тип рекуррентного поведения.

Что касается стохастических моделей. То в доступной литературе по моделям технического обслуживания с дискретным временем процесс износа оборудования рассматривается преимущественно как цепочка Маркова.

Серник и Маркус [3] получили оптимальную политику и связанную с ней стоимость для двумерной задачи марковской замены с частичными наблюдениями. Они показали. Что в бесконечном горизонте оптимальная функция дисконтированных затрат кусочно-линейна. А также предоставили формулы для вычисления стоимости и политики.

В [4], авторы предполагают. Что износ машины не является дискретным процессом. Но его можно смоделировать как непрерывный по времени марковский процесс. Поэтому единственный способ улучшить качество-это заменить машину на одну новую. Они выводят некоторые условия стабильности системы в рамках простого класса политики планирования/замены в реальном времени.

Некоторые модели приближаются к оценке интервалов инспектирования для поэтапного износа контролируемых сложных компонентов в системе с серьезными затратами времени простоя с использованием марковской модели (см.

, например, [5]).

В работе [6] проблема рассматривается с точки зрения инженерии надежности. Разрабатывающей стратегии замены. Основанные на прогнозном техническом обслуживании. Кроме того, в работе [7] авторы сформулировали стохастический вариант задачи замены параллельных машин. Они проанализировали структуру оптимальных стратегий в рамках общих классов функций восстановительных затрат.

Другим важным подходом. Получившим решение задачи. Является геометрическое программирование [8]. В своем предложении автор обсуждает применение этого метода к решению задачи замещения с бесконечным горизонтом и при определенных обстоятельствах получает замкнутое решение оптимизационной задачи.

Решение этой проблемы при наличии бюджетных ограничений можно найти в работе [9]. В своей работе авторы предлагают двойную эвристику для решения больших. Реалистичных задач путем первоначального ослабления бюджетных ограничений.

По сравнению с методами моделирования. Dohi et al. [10], предлагают методику. Основанную на получении первых двух моментов распределения дисконтированных затрат. А затем аппроксимируют базовую функцию распределения тремя теоретическими распределениями с помощью моделирования методом Монте-Карло.

Наиболее важными пионерами в применении моделей динамического программирования в задачах замены являются: Беллман [11], Уайт [12], Дэвидсон [13], Уокер [14] и Берцекас [15]. В последнее время марковский процесс принятия решений успешно применяется к проблеме замещения животных как продуктивной единицы (см.. Например, [16-18]).

Хотя моделирование и оптимизация задачи замещения с использованием марковских процессов принятия решений является темой широко известной [19]. Однако существует значительное количество сведений о теории стохастических матриц возмущений (см. [20-23] и ссылки в них). Рассматривая все ссылки. Проблема представлена в следующем разделе.

3. Постановка задачи

Начнем с определения дискретно-временного марковского процесса принятия решений с конечным пространством состояний Z состояний z1, z2, ···, zz, где на каждом этапе s = 1, 2, ··· аналитик должен принять решение d между ξ возможными. Обозначим через z(n) = z и d(n) = di состояние и решение. Принятые на этапе n соответственно. Тогда система переходит на следующем этапе n + 1 в следующее состояние j с известной вероятностью, заданной

(1)

Когда происходит переход. За ним следует вознаграждение, а выигрыш дается

в состоянии z после принятия решения dk.

Для каждой политики соответствующая марковская цепь эргодична. Тогда стационарные вероятности этой цепи задаются

и проблема состоит в том. Чтобы найти политику, для которой ожидаемый выигрыш

(2)

это максимум. В этой системе интервал времени между двумя переходами называется стадией.

Оптимальная политика определяется как политика. Которая максимизирует (или минимизирует) некоторую предопределенную целевую функцию. Метод оптимизации (т. е. метод получения оптимальной политики) зависит от формы целевой функции и может привести к различным альтернативным целевым функциям. Выбор критерия зависит от того. Является ли горизонт планирования конечным или бесконечным [1].

В нашем предложении мы рассматриваем единую машину и регулярные временные интервалы. Следует ли ее хранить в течение дополнительного периода или она должна быть заменена новой. Исходя из вышеизложенного. Пространство состояний определяется и, наблюдая за состоянием. Следует принять меры в отношении машины. Чтобы сохранить его. По крайней мере. На дополнительной стадии или заменить его в конце стадии.

Экономическая отдача от системы будет зависеть от ее эволюции и от того. Будет ли машина сохранена или заменена. В этом предложении это представлено вознаграждением в зависимости от состояния и действия. Заранее определенного. Если действие replace принято. То мы предполагаем. Что замена происходит в конце этапа с известной стоимостью. Горизонт планирования неизвестен и считается бесконечным. Кроме того. Все этапы имеют одинаковую длину.

Оптимальным критерием. Используемым в этом документе. Является максимизация ожидаемого среднего вознаграждения за единицу времени, заданного

(3)

где-предельная вероятность состояния в соответствии с политикой.

Традиционно динамическое программирование признается методом решения сложных задач на основе их декомпозиции в более простые модели. Кстати, эта методика применяется в тех случаях. Когда задачи имеют оптимальную подструктуру.

Базовая модель содержит два основных элемента: а) дискретную динамическую систему. Эволюционирующую во времени. Б) функцию затрат. Аддитивную во времени [15]. Система развивается под влиянием про решений выраженных через переменные состояния и имеет вид

(4)

где k — дискретизированный индекс времени.

xk — это состояние системы и сохранение прошлой информации. Которая имеет отношение к будущей оптимизации.

uk-это переменная решения. Которая должна быть выбрана во времени k.

wk — это случайный параметр решения (или шум).

N — горизонт планирования.

А fk — это функция. Описывающая систему. Функция затрат является аддитивной. Поскольку стоимость времени k накапливается с течением времени. Общая стоимость составляет

(5)

где конечная стоимость в конце процесса. Хотя, поскольку приналичииwk эта стоимость . Как правило. Является случайной величиной и нет никакого смысла оптимизировать ее как пунктуальную величину. В данном случае используется ожидаемая стоимость

(6)

ожидаемое значение применяется к объединенному распределению случайных величин. Участвующих в процессе. Оптимизация осуществляется по переменным решения u0, u1, ···, uN1. В свою очередь. Случайные величины uk выбираются с обновленной информацией о текущем состоянии переменной xk либо с точными. Либо с приближенными значениями. В данном разделе предлагается использовать методологию динамического программирования для решения задачи замещения с использованием функции вознаграждения. Построенной из функций затрат и доходов.

4. Функционал. Связанный с Вознаграждением

В этом разделе мы представили задачу замещения как динамическую систему. Которая эволюционирует по определенным законам. Включенным в матрицы вероятностей перехода. В этом случае функция стоимости системы в состоянии i равна g(i) и удовлетворяет тому, что

(7)

это означает. Что стоимость состояния i меньше стоимости в состоянии i + 1 и состояние 1 соответствует наилучшему состоянию оборудования. Z представляет все состояния системы. Как правило. Между каждым периодом эксплуатации оборудование может ухудшаться или оставаться неизменным. Тогда для стохастического случая вероятности перехода равны

(8)

Предполагается. Что в начале следующего периода. Состояние оборудования известно и два следующих решений должны быть выбраны: а) поддержания работы оборудования на следующий период и Б) ремонт оборудования. Принять состояние 1 на сумму р. Еще одна важная гипотеза заключается в том. Что после того как оборудование отремонтировано. Состояние 1 гарантированно. По крайней мере. Один период. И в последующие периоды. Оборудование может ухудшаться по переходных вероятностей РIJ на.

Учитывая вышеизложенное. Задача состоит в том. Чтобы определить уровень износа (состояние). При котором получается меньшая стоимость ремонта машины. Следовательно. Наилучшие выгоды по отношению к стоимости будут получены в будущем.

Хотя простота динамического программирования для представления состояний является преимуществом. Верно также и то. Что вычислительная сложность возрастает. Когда учитывается больше возможностей системы. Наш подход состоит из функционала вознаграждения. Который включает в себя расходы и выгоды. Пропорциональные оборудованию с двумя состояниями (сохранить и заменить). Хотя более двух состояний могут быть разумными.

Формально функция вознаграждения такова

(9)

где представлены доходы. Полученные при выполнении процесса в состоянии z и принятии решения d. Аналогично, выражение

(10)

представляет собой затраты. Произведенные при техническом обслуживании или замене оборудования. Когда оборудование работает поэтапно до его замены. Здесь m(s) представляет собой затраты на техническое обслуживание. Когда оборудование находится на стадии s. K-постоянные затраты на замену оборудования. P-цена покупки нового оборудования. А q(s) — стоимость спасения. Когда оборудование находится на стадии s. Константа γ равна

(11)

Предположим теперь. Что затраты ограничены и ξ таково, что

Затем, используя уравнение (9). Предлагается следующий функционал

(12)

оценить ожидаемое вознаграждение от процесса на всех его этапах. Если можно доказать (см. [15]), что при таком подходе коэффициент дисконтирования β, 0

(13)

Позволь

(14)

здесь говорится. Что политика является β-оптимальной.

Тогда политика β-оптимальна. Так как вознаграждение β-дисконтировано является максимальным для каждого начального значения. Это предложение может быть формализовано в следующих теоремах Теорема 4.1: Функционал

удовлетворяет оптимальному значению.

Доказательство: Доказательство тривиально. Этот подход является вариантом уравнения оптимальности. Предложенного и продемонстрированного Россом [24], где функционал записывается через функцию вознаграждения в виде

.

Теорема 4.2: Пусть политика стационарна, поэтому. Если процесс находится в состоянии z. Решение d выбирается для того. Чтобы максимизировать функцию

Так

Доказательство: Переписав функционал уравнения (11). Мы снова имеем вариант уравнения оптимальности Росса [24], который демонстрируется в этой ссылке.

5. Числовой Пример

Рассмотрим вариацию примера. Приведенного в работе [2], доходы приведены в таблице 1.

В таблице 2 приведены вероятности перехода. Описанные в работе [1

Затраты на техническое обслуживание являются переменными на каждой стадии. Увеличивающимися со скоростью 1%. Затраты на техническое обслуживание на стадии s = 1 составляют m(1) = 10 000. Спасательное значение также изменяется на каждом этапе. Уменьшаясь со скоростью 10%. Так как первый этап равен q(1) = 2000. В таблице 3 приведены некоторые затраты на техническое обслуживание и аварийно-спасательные работы для первых 40 ступеней.

Таблица 3. Затраты на техническое обслуживание. М(ы) и аварийные значения.

Оборудование-K = 3000, а цена покупки нового оборудования-p = 10 000. Рассматривается дисконтированный коэффициент β = 0,9 и горизонт планирования s = 40.

В таблице 4 показаны итерации с первых s = 40 этапов. Обратите внимание, что от s = 1 до s = 25 результат заменяется в состоянии z = 1 и сохраняется в состояниях z = 2, 3. От s = 26 до s = 33 результат заменяется в состояниях z = 1, 2 и сохраняется в состоянии z = 3. От s = 34 решение заменяется в трех состояниях. Эти результаты получены потому. Что затраты на техническое обслуживание увеличиваются. А спасательные значения уменьшаются от одной стадии к другой.

6. Выводы

Для задач замещения с конечным горизонтом планирования наиболее широко используется динамическое программирование; это связано с тем. Что с помощью этого метода можно естественным образом вывести оптимальное решение через функциональные формы.

В нашем подходе мы исследуем проблему замены. Решаемую динамическим программированием. И предлагаем новый функционал. Который включает в себя функцию вознаграждения. А также полезную информацию. Такую как доходы. Затраты на техническое обслуживание. Постоянные затраты на замену оборудования. Покупную цену и стоимость утилизации. Доказаны две теоремы. Связанные с этой новой функцией-

тион. Будущая работа могла бы включать в себя больше решений (не только сохранить и заменить). Эти решения усложняют решение. Но и больше похожи на реальную жизнь. Другим вкладом может быть увеличение количества оборудования. Доходов и расходов. Связанных с проблемой замены.

Ева Селена Эрнандес Гресс. Оскар Монтаньо Аранго. Хосе Рамон Корона Армента. Антонио Освальдо Ортега Рейес Эта модель была разработана без учета конкретного вида промышленности. Но может быть использована в перерабатывающей промышленности. Сейчас мы работаем над валидацией модели в некоторых перерабатывающих отраслях нашего региона.

РЕКОМЕНДАЦИИ

  1. А. Кристенсен. “Учебник по управлению стадом: динамическое программирование и Марковский процессhttp://www.husdyr.kvl.dk/ark/pdf/notat49.pdf   [Время цитирования:4]
  2. Р. А. Говард. “Динамическое программирование и марковские процессы”. The MIT Press. Cambridge, 1960.  ]
  3. E. L. Sernik and S. Marcus. “Optimal Cost and Policy for Markovian Replacement Problemdoi:10.1007/BF00940042   [Время цитирования:1]
  4. S. P. Sethi, G. Sorger and X. Zhou, “Stability of RealTime Lot Scheduling and Machine Replacement Policies with Quality Levels», IEEE Transactions on Automatic Control, Vol. 45, No. 11, 2000, pp. 2193-2196. doi:10.1109/9.887687   [Время цитирования:1]
  5. J. D. Sherwin and B. Al-Najjar, “Practical Models for Conditions-Based Monitoring Inspection Intervals”, Journal of Quality in Maintenance Engineering, Vol. 5, No. 3, 1999, pp. 203-209. doi:10.1108/13552519910282665   [Время цитирования:1]
  6. E. Льюис, “Введение в теорию надежности”, Wiley, Singapore City, 1987.   [Время цитирования: 1]
  7. С. Чайлдресс и П. Дюранго-Коэн, “О задачах параллельной замены машин с общими функциями затрат на замену и стохастическим ухудшением”, Военно-морская исследовательская логистика, Том 52, № 5, 1999,   с. 402-419. ]
  8. T. Cheng, “Оптимальная замена стареющего оборудования с использованием геометрического программирования”, International Journal of Production Research, Vol. 30, No. 9, 1999, pp. 2151 — 2158. doi:10.1080/00207549208948142   [Время цитирования: 1]
  9. N. Karabakal, C. Bean and J. Lohman, “Решение больших проблем замещения с бюджетными ограничениями”, The Engineering Economist, Vol. 4, No. 5, 2000, pp. 290-308. doi:10.1080/00137910008967554   [Время цитирования:1]
  10. T. Dohi, et al.. “A Simulation Study on the Discounted Cost Distribution under Age Replacement Policy  . 134-139.]
  11. Р. Беллман. “Политика замены оборудования”, Журнал Общества промышленной и прикладной математики, Том 3, № 3, 1955, стр. 133-136.  ]
  12. D. White, “Dynamic Programming   [Время цитирования:1]
  13. Д. Дэвидсон. “Политика капитального ремонта для ухудшающегося оборудования”, В: A. Jardine, Ed., Operational Research in Maintenance, Manchester University Press, New York, 1970, pp  . 1-24.]
  14. J. Walker, “Графический анализ для замены машин”, International Journal of Operations and Production Management, Vol. 14, No. 10, 1992, pp. 54-63. doi:10.1108/01443579410067252   [Время цитирования:1]
  15. D. Bertsekas. “Dynamic Programming and Optimal Control   [Время цитирования:3]
  16. L. Plá, C. Pomar and J. Pomar, “Модель Марковской свиноматки, представляющая продуктивную продолжительность жизни стадных свиноматок”, Agricultural Systems, Vol. 76, No. 1, 2004, pp. 253-272.
  17. L. Nielsen and A. Kristensen. “Finding the K Best Policies in a Finite-Horizon Markov Decision Processdoi:10.1016/j.ejor.2005.06.011
  18. L. Nielsen, et al., “Оптимальная политика замещения молочных коров на основе ежедневных измерений удоя”, Journal of Dairy Science, Vol. 93, No. 1, 2009, pp. 75-92. doi:10.3168/jds.2009-2209
  19. F. Hillier and G. Lieberman. “Introduction to Operations Research  ]
  20. П. Шрайнер и Э. Дорн. “Матрица отклонений марковской цепи непрерывного времени
  21. С. Мейер, “Чувствительность стационарного распределения цепи Марковаdoi:10.1137/S0895479892228900
  22. М. Аббад, Дж.Филар и Т. Р. Белецкий, “Алгоритмы для сингулярно возмущенной цепи Маркова”, Труды 29-й конференции IEEE, Гонолулу, 5-7 декабря 1990 г.. С. 1402-1407.
  23. E. Файнберг. “Ограниченные дисконтированные процессы принятия решений и гамильтоновы циклыdoi:10.1287/moor.25.1.130.15210
  24. S. Ross, “Applied Probability Models with Optimization Applications   [Время цитирования:2]