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

На правах рукописи

! Поляков Александр Николаевич

!

РАЗРАБОТКА И АНАЛИЗ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ И

АЛГОРИТМОВ ОПЕРАТИВНО-КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ФАРМАЦЕВТИЧЕСКОГО ПРОИЗВОДСТВА

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в экономике)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Томск-2003

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

Ведущая организация: Новосибирский государственный технический университет, г.Новосибирск

Защита состоится 24 декабря 2003 г., в 15-00 на заседании диссертационного совета Д212.269.06 при Томском политехническом университете по адресу: г. Томск, ул. Советская, 84, ауд. 214.

С диссертацией можно ознакомиться в библиотеке Томского политехнического университета по адресу: 634034, г.Томск, ул. Белинского, 53.

Автореферат разослан "21" ноября 2003 г.

Научный руководитель:

доктор технических наук, профессор Ямпольский Владимир Захарович

Официальные оппоненты: доктор технических наук, профессор

Ехлаков Юрий Поликарпович

кандидат технических наук, доцент Камышников Владимир Андреевич

Ученый секретарь диссертационного совета

Сонъкия М. А.

Общая характеристика работы

Актуальность работы. В последнее время руководители российских предприятий вслед за своими западными коллегами все чаще осознают необходимость внедрения компьютерных систем планирования производственных ресурсов класса МИРИ/ЕЮ5. Использование таких систем позволяет достичь конкурентных преимуществ за счет оптимизации бизнес-процессов и материально-финансовых потоков на основе планирования и контроля всей деятельности предприятия, что в итоге приводит к снижению себестоимости, повышению качества выпускаемой продукции, улучшению обслуживания потребителей за счет полного и своевременного исполнения поставок.

Одной из важнейших составляющих процесса управления в системах планирования производственных ресурсов является оперативно-календарное планирование (ОКП) производства, представляющее собой разработку оперативных планов и графиков изготовления и выпуска продукции на короткие отрезки времени: месяц, декаду, пятидневку, сутки.

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

От тога насколько оптимально~будет составлен отератавно-календарньтй график производства в соответствии с этими целями, зависит эффективность планирования всех материально-финансовых ресурсов предприятия с помощью компьютерной системы планирования производственных ресурсов.

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

Кроме того, изначально в алгоритмах решения задач ОКП время выполнения операций и другие параметры рассматривад^ь^к^^етм^^исла^о есть

БИБЛИОТЕКА I О»" I

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

Внедрение на Томском химико-фармацевтическом заводе (ТХФЗ) системы планирования производственных ресурсов ШйэпСОМ показало, что особенности процессного производства, а также нечеткость некоторых целей и параметров планирования, которые, в общем, присущи и дискретному производству, сильно влияют на постановку и решение задачи ОКП. Стандартные методы, заложенные в системы МИРИ, в т.ч. и в 1п<Ьг:СОМ, оказались неспособными решить задачу ОКП производства ТХФЗ на более или менее приемлемом уровне.

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

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Провести анализ особенностей фармацевтического производства.

2. Построить математическую модель ОКП фармацевтического производства.

3. Разработать алгоритмы решения задач ОКП фармацевтического производства для предложенной модели.

4. Создать программное обеспечение для решения задач ОКП фармацевтического производства.

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

Основные положения, выносимые на защиту:

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

2. Модификация эвристического правила приоритетов ЕББ, разработанная для решения задачи ОКП фармацевтического производства.

I*» г

3. Модификация метода учета неопределенностей ОКП, основанного на математическом аппарате теории нечетких множеств.

4. Автоматизированная система оперативно-календарного планирования фармацевтического производства.

Научная новизна данной диссертационной работы заключается в следующем:

1. Построена оригинальная математическая модель ОКП фармацевтического производства.

2. Разработана модификация эвристического правила EDD применительно к поставленной задаче ОКП.

3. Разработана модификация метода учета неопределенностей ОКП фармацевтического производства.

Практическая ценность. Разработанная модификация алгоритма планирования по правилу EDD позволяет строить допустимые (с точки зрения предложенной математической модели) оперативные трафики производства с минимальным временем межоперационного пролеживания. При этом трудоемкость разработанного алгоритма настолько низка, что его программная реализация позволяет строить на ПЭВМ производственные графики любой сложности (в разумных пределах) за время, не превышающее нескольких минут.

Разработанный алгоритм метода учета неопределенностей ОКП фармацевтического производства позволяет увеличить критерий эффективности ОКП в несколько раз по сравнению с алгоритмом, построенным по методу С.Аллета.

Созданное программное обеспечение может использоваться для решения задач ОКП либо в составе системы планирования производственных ресурсов, либо автономно. Эффективность использования результатов работы в деятельности предприятий подтверждено в ходе промышленной эксплуатации разработанного программного обеспечения на Томском Химфармзаводе.

Апробация работы. Результаты работы представлены на 8 конференциях и симпозиумах, в том числе 5 международных: Международная молодежная школа-семинар «Будущее информатики, космического, авиационного и медицинского приборостроения», г.С.-Петербург, 2003; Международный форум «Новые инфокоммуникационные технологии: достижения, проблемы, перспективы», г.Новосибирск, 2003; Международная научно-практическая конференция «Современные техника и технологии», г.Томск, 2003; Международная научно-техническая конференция «Наукоемкие технологии и интеллектуальные системы», Москва, 2003; Korean-Russian international symposium on Science & Technology, Ulsan, 2003; Всероссийская конференция "Современные проблемы информатизации", г.Воронеж, 2003; Всероссийская конференция «Российская школа и Интернет», Москва, 2003; Региональная научно-практическая конференция студентов «Молодежь и современные информационные технологии», г.Томск, 2003.

Магистерская диссертация автора на тему «Исследование возможности применения нечеткой логики в принятии управленческих решений», в которой

отражены начальные этапы исследования, заняла 1-е место на Всероссийском конкурсе на лучшую научную работу студентов в 2001 году. По результатам работы опубликовано 9 печатных работ. Достоверность результатов обеспечивается строгим применением математических методов, тестированием программного обеспечения на реальных задачах ОКП фармацевтического производства, внедрением разработанного программного обеспечения.

Личный вклад автора. Диссертация написана с использованием результатов, полученных лично автором. Большинство опубликованных работ написаны без соавторов.

1. Автором построена математическая модель ОКП фармацевтического производства.

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

3. Используя разработанную модификацию правила ЕГЮ, создан алгоритм для решения задач ОКП, позволяющий получить такие же результаты, как и при планировании с помощью алгоритма по схеме метода ветвей и границ, но с существенно меньшими затратами вычислительных ресурсов.

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

5. Программное обеспечение для оперативно-календарного планирования производства разработаны лично автором.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и четырех приложений. Диссертация содержит 144 страницы текста, 30 рисунков, 18 таблиц, 148 библиографических ссылок.

^Содержание работы

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

В первой главе рассмотрены характеристики современного фармацевтического производства и особенности его оперативно-календарного планирования, в результате чего построена математическая модель и сделана формальная постановка задачи ОКП фармацевтического производства.

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

зависимость качества продукции от длительности операций; методика расчета длительности производственного цикла; межоперационные перерывы; непрерывность операций;

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

В задаче присутствуют:

Ок - типы оборудования, к = 1.. .К. Имеется И к единиц оборудования каждого типа, каждая единица оборудования обозначается Мкр, р = 1 ...1^.

.Г( - работы, I = 1...и. Каждая работа ^ состоит из Н операций, каждая операция обозначается Оу, 3 = 1...М;.

Каждая операция Ои может выполняться на определенном типе оборудования, соответственно, каждая операция характеризуется набором чисел (М, к}. Далее в тексте, если будет необходимо уточнить, на каком типе оборудования может выполняться операция Ои, эта операция будет обозначаться как Оик, где к - тип оборудования.

ОД) - время выполнения работы ^. - время выполнения операции Оу.

гч - время начала операции Оу - определяется процедурой (алгоритмом) планирования. Работа I; начинается в момент гп, то есть в момент начала 1-ой операции этой работы.

С, - время окончания работы ^ (время окончания последней операции в этой работе).

В различных существующих на сегодняшний день алгоритмах планирования производства требуемое время окончания работ задается единственным числом <1,. При этом подразумевается, что если время окончания работы меньше либо равно то такой график является допустимым, если же время окончания работы хоть немного превысило то такой график является полностью недопустимым. Такая постановка вопроса в реальном производстве встречается редко. Как правило, существует несколько возможных значений требуемого времени окончания каждой работы. Эти значения принадлежат интервалу ¡ь 3 ¡я], где 2л. является желательным временем окончания работы 1;, 3 ¡я - предельный срок окончания работы Значения времени окончания работы внутри интервала 3 ; не являются равпозначными - чем ближе время окончания к желательному, тем выше удовлетворенность лиц, принимающих решения (ЛПР) временем окончания работы, и наоборот, чем ближе время окончания к предельно допустимому, тем ниже удовлетворенность. Таким образом, понятие требуемого времени окончания работ является размытым, и наиболее подходящими способами его моделирования являются функции принадлежности.

Функция принадлежности Б,-, выражающая степень удовлетворенности ЛПР временем С; окончания работы Л„ задается с помощью нечеткого интервала 2 ; (см. рисунок 1).

Рисунок 1. Степень удовлетворенности ЛПР временем окончания работы

Качество выполнения операции соответствует качеству получаемого в результате этой операции полфабриката или готового продукта. Для количественной оценки качества предложено использовать интервал действительных чисел [0 ... 1]. Чем выше качество продукта, тем ближе к единице значение параметра качества. Нулевое значение параметра означает его недопустимость, то есть брак; значение качества, равное единице означает максимально достижимое качество.

Зависимость качества операции Оц от ее длительности предложено описывать с помощью функции принадлежности (Зц.

Как правило, качество операции тем выше, чем больше длительность операции в рамках некоторого интервала времени, соответственно, функция является возрастающей на некотором интервале. Эта функция определяется с помощью экспериментов и в различных производственных средах может иметь разнообразный вид, но наиболее часто зависимость качества от длительности является линейной. Поэтому функцию <3„ можно задать с помощью нечеткого интервала Ц:

1 ч= [1 ¡¡и < р]-

С?д равно нулю при значениях Ц меньших или равных Т ф и С^ равно единице при значениях ^ больших или равных Т При значениях лежащих в интервале [Т Т уц], линейно возрастает от нуля до единицы (см. рис. 2).

В фармацевтическом производстве каждая операция влияет на качество готового продукта, при этом хорошее качество одной операции какой-либо работы не может компенсировать плохое качество другой операции этой работы. Поэтому общее качество 0(1;) работы I, соответствует наихудшему качеству входящих в нее операций:

0(:Г;) = тт(<Зв).

0.. 1

0.5-

Рисунок 2. Зависимость качества операции от ее длительности

Выбор длительности операций, при которой будет обеспечено максимальное качество, не всегда оправдан, так как это может повлечь за собой неудовлетворенность временем окончания работ, либо вообще приведет к тому, что будут нарушены предельные сроки окончания работ. Поэтому при календарном планировании фармацевтического производства необходимо найти компромисс, обеспечивающий максимальное качество при максимальной удовлетворенности временем окончания работ - в современных рыночных условиях выполнение производственной программы в установленные сроки так же важно, как и достижение хорошего качества продукции. В связи с этим удовлетворенность 8(1;) ЛПР планированием работы I; определяется меньшим из значений параметров качества работы и удовлетворенности сроками выполнения работы:

8аО = тт[ОД), О,].

Целью ОКЛ является наибольшая степень удовлетворенности как можно большим количеством работ, поэтому критерием эффективности календарного планирования является степень удовлетворенности в всем производственным графиком, которая вычисляется как среднее арифметическое степеней удовлетворенности всеми работами:

и

С= 151_

-Ц--

При этом также необходимо знать минимальное значение Б,™ удовлетворенности 8(.Т;) ЛПР планированием всех работ:

8ГО,„ = тшрЭД)] для VI.

Значение 8т;п, равное нулю, не допустимо, так как независимо от средней удовлетворенности Б всем производственным графиком, в графике не должно быть работ, запланированных с качеством операций, равным нулю, либо время окончания которых превышает предельно допустимые сроки. Таким образом, если Бпйп равно нулю, то производственный график считается недопустимым. Среди всех графиков с 8т;ш большим нуля, наиболее предпочтительным является график с наибольшим значением критерия эффективности

Таким образом, целями ОКП современного фармацевтического производства являются:

Smm>0, S —> max.

Не в ущерб критерию S необходимо свести время межоперационного про-леживания к минимуму, то есть необходимо обеспечить условие:

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

Исследуемая задача в математическом отношении относится к классу 11П-трудных, поэтому для ее решения в основном используются эвристические правила приоритетов.

Поскольку в большинстве реальных производственных систем ограничения по предельным срокам окончания работ присутствуют (так же, как и в нашей задаче), то наиболее универсальным и часто используемым на практике является правило EDD, т.к. его использование позволяет добиться наиболее оптимальных результатов планирования в производственных системах, в которых работы должны завершиться до некоторых требуемых времен окончания: rij + t(J;) < d, для V i = 1...U.

Например, в системе InfonCOM, активно продвигаемой в настоящее время фирмой Epicor Software на российском рынке и используемой на ТХФЗ для планирования производственных ресурсов, реализовано только это эвристическое правило.

Алгоритм по правилу EDD не способен работать с нечеткими временами выполнения операций и требуемыми временами окончания работ, поэтому необходимо зафиксировать на некотором уровне желаемое качество операций и желательную степень удовлетворенности ЛПР временем окончания работ.

В результате планирования производственных заданий цеха ТХФЗ с качеством операций, равным 1 и 0, независимо от качества операций получилось большое время межоперационного пролеживания - более 5500 часов, что недопустимо в условиях фармацевтического производства. Анализ получившихся в результате планирования по правилу EDD времен межоперационного пролеживания, а также предложения по их уменьшению будут представлены в следующей главе.

В результате планирования с длительностью операций, обеспечивающим наилучшее качество, т.е. Q,j = 1, более трети всех работ превысили желательное время окончания, а несколько работ превысили предельно допустимое время окончания, т.е. получившийся трафик является недопустимым. Это произошло потому, что при заданных параметрах планирования оказывается невозможным выдержать такую длительность операций, которая бы обеспечивала максимальное качество операций.

При планировании работ с качеством операций, равным 0, все работы закончились раньше предельных конечных сроков, то есть для производственных заданий цеха ТХФЗ в этом случае существуют допустимые решения, но очевидно, что планирование с длительностью операций, приводящей к нулевому качеству, т.е. браку, недопустимо.

Таким образом, значение параметра качества операций, дающее оптимальное значение критерия эффективности Б, находится в интервале (0, 1], и для поиска допустимого производственного графика с наибольшим возможным значением критерия эффективности необходимы специальные методы, которые позволяются работать с параметрами планирования, заданными нечетко.

Наиболее близкой к этой задаче, по мнению автора данной работы, является проблема поиска оптимального значения критерия эффективности, который бы обеспечивал компромисс между качеством операций и удовлетворенностью сроками выполнения работ, рассмотренная бельгийским исследователем С. Ал-летом.

Суть решения этой задачи состоит в следующем. Обозначим задачу ОКП символом (Р). Пусть (Р)а - подзадача задачи (Р), полученная путем добавления к задаче (Р) двух ограничений:

1. а-уровень для всех нечетких множеств 31 с функциями принадлежности Д (для V 1 = 1 ...Ц), моделирующих отношение предпочтения требуемых времен окончания всех работ.

2. а-уровень для всех нечетких множеств Ту с функциями принадлежности (для V 1 = 1...и, ] = 1 ...N1), моделирующих отношение предпочтения качества всех операции.

Основная идея метода С.Аллета состоит в том, чтобы используя принцип дихотомии, последовательно решать подзадачи (Р)а (значение а фиксировано на интервале [0, 1]) решаемой задачи ОКП (Р) до тех пор, пока не будет достигнута граница точности е.

В результате планирования производства цеха ТХФЗ с помощью алгоритма, построенного по методу С.Аллета, минимальное значение удовлетворенности 8(10 ЛПР планированием работ получилось больше нуля (Бп,™ = 0.19), поэтому полученный график является допустимым, но значение критерия эффективности 8 оказался равен значению 8т;„ (0.19), что является низким показателем. Это обусловлено тем, что в результате планирования по методу С.Аллета, качество <3у всех операций О,; в производственном графике получается одинаковым, причем оно будет равно наихудшему возможному качеству. Следовательно, в случаях, если в производственном графике узкие места (работы с небольшой разницей между фактическими и требуемыми временами окончания) находятся ближе к началу горизонта планирования, что в условиях реального производственного планирования бывает часто, то метод С. Аллета должен привести к тому, что значение критерия эффективности Б окажется ниже максимально возможного значения.

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

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

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

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

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

Ои Ой Ов Ой

м^Г

M«

М43

Рисунок 3. Схема метода ветвей и границ для календарного планирования

операций

Как и ожидалось, алгоритм по схеме метода ветвей и границ оказался трудоемким в вычислительном плане: на ПЭВМ время планирования 64 работ составляет более 10 часов - за это время входные данные планирования могут оказаться не актуальными. Но анализ циклограмм и результатов применения различных разработанных модификаций алгоритмов по схеме метода ветвей и границ показал, что результаты планирования во многом зависят от планирова-

ч

I

I (

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

Поэтому предложено модифицировать правило ЕББ таким образом, чтобы первые операции планировались не как можно раньше, как все последующие операции, а несколько позже возможного раннего времени начала каждой пер-,■« вой операции. При этом имеется несколько возможностей для планирования

первых операций - начиная от планирования как можно позже, и заканчивая < планированием как можно раньше.

1111111111111111111

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Рисунок 4. Пример планирования операций по правилу ЕББ с различными возможными временами начала первых операций

Рассмотрим для примера рисунок 4. Серыми прямоугольниками обозначены уже запланированные операции. Допустим, необходимо затгланировать операцию длительностью 4 часа. В данном случае имеется 3 возможности для планирования 1-ой операции: самое позднее возможное время начала равно 14 часам - в этом случае коэффициент П изменения времени начала первых операций равен 0; более ранний возможный срок начала равен 9 часам — в этом случае П = 1; и, наконец, самое раннее возможное время начала равно 3 часам - в этом случае П = 2.

При этом у некоторых работ можно уменьшить время межоперационного пролеживаяия, не увеличивая при этом время окончания работ. Для этого после планирования всех операций с помощью алгоритма по правилу ШЮ, необходимо все операции, начиная с предпоследней, передвинуть к последующим операциям, то есть увеличить время начата каждой операции (кроме последней):

гад.,, (ги - д для V1 = 1 ..и,] = 2-.Ni.

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

Анализ результатов работы такого алгоритма показал, что планирование по правилу Е1® со сдвигом операций и с коэффициентом П изменения времени начала первых операций дает такие же результаты, как и планирование с

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

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

Трудоемкость алгоритма, использующего правило ЕОБ со сдвигом операций и с коэффициентом П изменения времени начала первых операций, значительно меньше трудоемкости алгоритма, реализованного по схеме метода ветвей и границ - такой алгоритм может построить на ПЭВМ производственный график любой сложности (в разумных пределах) за время, не превышающее нескольких минут.

Четвертая глава посвящена разработке и анализу алгоритмов решения задач ОКП фармацевтического производства в нечетких условиях.

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

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

работы с Д1 р по Л

..х

Рисунок 5. Блок-схема алгоритма модифицированного метода С.Аллета

Введем следующие обозначения:

х - группа работ;

а" - оптимальное значение параметра а для группы работ х;

.Пр - первая работа группы х; - последняя работа группы х.

Блок-схема алгоритма модифицированного метода С.Аллета представлена на рис. 5.

Для анализа алгоритма, построенного по разработанной модификации метода С. Аллета, этот алгоритм был использован для оперативно-календарного планирования производства цеха ТХФЗ в одном периоде.

В результате планирования с помощью алгоритма модифицированного метода С.Аллета с использованием правила ЕОБ со сдвигом операций и коэффициентом П изменения времени начала первых операций сумма времени межоперационного пролеживания равно нулю, а критерий эффектвности Б увеличился почти в 4 раза: с 0.19 до 0.59.

Для анализа эффективности предложенных алгоритмов они были протестированы на реальных данных планирования производства ТХФЗ в 18 периодах. Тесты показали, что стандартное правило ЕВБ в большинстве случаев дает производственный график с существенным временем межоперационного пролеживания даже в месяцах с небольшой загрузкой производственных мощностей. При планировании работ с помощью разработанной модификации правила ЕББ - со сдвигом операций и коэффициентом П изменения времени начала первых операций — удается либо вообще свести время межоперационного пролеживания к нулю, либо значительно его уменьшить - в несколько десятков раз. При этом практически всегда удается сохранить такую же минимальную удовлетворенность (8Ш1П) производственным графиком.

Использование алгоритма, построенного по разработанной модификации метода С. Аллета, позволяет улучшить среднюю удовлетворенность ЛПР производственным графиком (параметр Б, являющийся критерием эффективности ОКП) по сравнению с алгоритмом стандартного метода С.Аллета, особенно в периодах с большой загрузкой производственных мощностей. Таким образом, тестирование разработанных алгоритмов четкого и печеткого планирования и их сравнение с существующими алгоритмами показало, что разработанные алгоритмы решают поставленную в главе I задачу оперативно-календарного планирования фармацевтического производства.

Разработанные алгоритмы ОКП фармацевтического производства реализованы в виде программного обеспечения (ПО) для ПЭВМ. Состав и структура разработанного ПО приведены на рисунке 6.

Рисунок 6. Состав и структура разработанного программного обеспечения

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

Разработанные алгоритмы ОКП реализованы в основном модуле программы. Результаты планирования выводятся в виде циклограммы производственных процессов. Численные результаты записываются в файл и выводятся в виде таблицы в интерфейсе программы.

Основные результаты работы

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

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

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

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

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

6. Разработана модификация метода учета неопределенностей ОКП фармацевтического производства, предложенного С.Аллетом, позволяющая в несколько раз повысить значение критерия эффективности решения задач ОКП.

7. Разработан алгоритм модифицированного метода С. Ал лета применительно к поставленной задаче ОКП.

8, Разработанные алгоритмы программно реализованы, экспериментально апробированы, что позволило осуществить оценку разработанных алгоритмов с точки зрения эффективности решения задач ОКИ фармацевтического производства.

9. Создано программное обеспечение для решения задач ОКП фармацевтического производства, внедренное на Томском Химфармзаводе и используемое в практической деятельности предприятия для оперативно-календарного планирования в составе системы планирования производственных ресурсов.

Основные положения диссертации изложены в следующих работах:

1. Воловоденко В.А., Поляков А.Н. Применение нечеткой логики в принятии управленческих решений. Депонированная научная работа, ВИНИТИ, 2003. -18 с.

2. Поляков А.Н. Принятие решений в нечетких условиях. Сборник трудов VTTI Международной открытой научной конференции "Современные проблемы информатизации". Воронеж, 2003. - с. 112.

3. Поляков А.Н. Анализ марковских процессов с нечетко заданными состояниями. Сборник тезисов докладов международной молодежной школы-семинара БИКАМП. С.-Петербург, 2003. - с. 86.

4. Поляков А.Н. Динамическое программирование с нечеткими параметрами. Сборник тезисов докладов V международной конференции «Наукоемкие технологии и интеллектуальные системы». Москва, 2003. - с.73-75.

5. Поляков А.Н., Воловоденко В.А. Разработка и анализ математических моделей принятия решений в условиях нечеткой информации. Кибернетика и вуз. Томск, 2003.

6. Поляков АЛ. Нечеткая оптимизация технических систем. Кибернетика и вуз. Томск, 2003

7. Поляков А.Н. Исследование возможности применения нечеткой логики в принятии решений. Сборник тезисов докладов международной конференции «Современные техника и технологии». Томск, 2003. - с.93-94.

8. Poliakov A. An example of fuzzy decision-making system. Proceedings of the International Conference Chorus. Ulsan, 2003. - p.91.

Поляков А. Один пример нечеткой системы принятия решений. Сборник тезисов докладов международной конференции Корус. Ульсан, 2003. - с.91.

9. Поляков А.Н. Планирование производственных ресурсов в условиях неопределенности. Сборник тезисов докладов международного форума «Новые ин-фокоммуникационные технологии: достижения, проблемы, перспективы». Новосибирск, 2003. - с. 159-160.

» 18 8 7 3

Формат 60x84/16. Объем 1 п. л. Печать трафаретная. Тираж 100. Заказ 896. Размножено ООО «Дельтаплан». Лицензия ИД N8 01282 от 22.03.2000.

564551 А 204780

Оглавление.

Введение.

Глава I. Постановка задачи оперативно-календарного планирования (ОКП) на фармацевтическом предприятии.

1.1 Характеристика современного фармацевтического производства

1.2 Особенности ОКП фармацевтического производства.

1.3 Математическая модель ОКП фармацевтического производства

В конце 90-х годов прошлого столетия в России плановая экономика сменилась рыночной. В результате экономической реформы предприятия России стремительно переместились из дефицитного рынка в конкурентный рынок, причем конкурировать пришлось с мировыми производителями, у которых соотношение цена/качество было предпочтительнее [3].

В решающей степени слабая конкурентоспособность российских предприятий объясняется внутренними факторами: уровнем технологий, состоянием организации производства, совершенством управления предприятием. Состояние этих факторов на отечественных предприятиях определяет высокий уровень затрат на производство, низкое качество выпускаемой продукции, негибкость взаимодействия с потребителями [9, 33], что в конечном счете обуславливает низкий спрос на продукцию, неудовлетворенность потребителей и проигрыш в конкурентной борьбе с иностранными компаниями.

Не является исключением и фармацевтическая индустрия. По данным отраслевого агентства RMBC (www.rmbc.ru) в конце 90-х годов доля иностранных производителей составляла 55-60% отечественного рынка лекарственных средств. Эта доля постоянно растет и к первому полугодию 2003 г. доля иностранных производителей достигла 68% [17].

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

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

Одной из важнейших составляющих процесса управления с помощью систем MRPII является оперативно-календарное планирование (ОКП) производства, представляющее собой формирование оперативных пооперационных производственных планов цеха на планируемый период [66]. Задачи ОКП в математическом отношении являются НП-трудными (задачи с нелинейной полиномиальной оценкой числа итераций), то есть время, затрачиваемое на решение, растет экспоненциально с ростом размерности задачи. Поэтому усилия исследователей были сосредоточены на разработке эвристических алгоритмов, предназначенных для решения различных задач планирования производственных ресурсов [123]. В последние десятилетия были достигнуты значительные результаты в разработке таких методов, однако подавляющее большинство работ явно или неявно были направлены на исследования методов ОКП дискретных производств [4, 10, 61]. Если в исследованиях и уделялось внимание планированию процессных (непрерывных) производств, к которым относится и фармацевтическая промышленность, то только в плане адаптации методов планирования дискретных производств [100].

Кроме того, изначально в этих алгоритмах время выполнения операций и другие параметры рассматривались как четкие числа, то есть совре5 менные системы производственного планирования основаны на принципе жесткого количественного определения целей и входных параметров. Практическая реализация этого принципа в реальных производственных системах весьма слаба, так как конкретные цели и условия производства зачастую не могут быть точно определены, то есть являются нечеткими [95]. Так как важнейшим вопросом управления является вопрос - до какой степени достигаются намеченные цели, то для решения задач производственного планирования правильней было бы использовать математический аппарат нечетких множеств. К этому в последнее время склоняются многие исследователи планирования производственных ресурсов (см., например, обзор [99]), но за редкими исключениями ([81]) эти исследования носили чисто теоретический характер, и об их применении на практике не сообщалось.

Внедрение на Томском химико-фармацевтическом заводе (ТХФЗ) системы класса MRPII InfonCOM (подробно об этой системе см. в разделе II.1) показало, что особенности процессного производства, а также нечеткость некоторых целей и параметров планирования, которые, в общем, присущи и дискретному производству, сильно влияют на постановку и решение задачи ОКП. Стандартные методы, заложенные в системы MRPII, в т.ч. и в Infor:COM, оказались неспособными решить задачу ОКП производства ТХФЗ на более или менее приемлемом уровне. Также во всех известных автору современных системах класса MRPII отсутствует возможность планирования с учетом нечеткости задания параметров и целей, что тоже затрудняет использование этих систем на практике. Неадекватность практического использования «четких» систем отмечают многие исследователи - см., например, [128]. Поэтому есть насущная необходимость в разработке методов ОКП, специально предназначенных для фармацевтических производств, учитывающих нечеткий характер целей и параметров планирования.

Объектом исследования в данной работе является система оперативно-календарного планирования фармацевтического производства, возможности ее усовершенствования с учетом особенностей фармацевтического производства и нечеткого характера целей и параметров планирования.

Предмет исследования - оперативные календарные планы фармацевтического производства.

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

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

Научная новизна исследования заключается в следующем:

1. Предложено использовать математический аппарат нечетких множеств для более адекватного формализованного описания и математической постановки задач ОКП фармацевтического производства.

2. Построена оригинальная математическая модель ОКП фармацевтического производства.

3. Разработаны эффективные алгоритмы ОКП, учитывающие неопределенность параметров и целей планирования.

Практическая значимость исследования состоит в том, что в ходе работы была создана автоматизированная система построения оперативно-календарных планов для ПЭВМ. В системе можно задавать параметры планирования, что позволяет строить любые оперативно-календарные планы фармацевтического производства. Длительность производственных процессов и требуемые времена выполнения можно задавать в нечетком виде, что позволяет получать более гибкие графики с учетом нечеткого характера це7 лей и параметров. Результаты исследования внедрены на Томском химфарм-заводе.

Разработанные алгоритмы могут оказаться полезными и при построении оперативно-календарных планов дискретных производств, например, в машиностроении. Вопрос применения разработанных в ходе работы моделей и алгоритмов в других производственных средах (не фармацевтике) требует дополнительных исследований.

Структура диссертационной работы.

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

В главе II исследованы существующие методы ОКП, применяемые для планирования фармацевтического производства. Обоснован выбор эвристического правила EDD [123] для планирования в четких условиях и метода, предложенного Самиром Аллетом [81], для планирования в нечетких условиях.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. Разработана модификация метода учета неопределенностей ОКП фармацевтического производства, предложенного Самиром Аллетом, позволяющая в несколько раз повысить значение критерия эффективности решения задач ОКП.

7. Разработан алгоритм по схеме модифицированного метода Сами-ра Аллета применительно к поставленной задаче ОКП.

8. Разработанные алгоритмы программно реализованы, экспериментально апробированы, что позволило осуществить оценку разработанных алгоритмов с точки зрения эффективности решения задач ОКП фармацевтического производства.

9. Создано программное обеспечение для решения задач ОКП фармацевтического производства, внедренное на Томском Химфармзаводе и используемое в практической деятельности предприятия для оперативно-календарного планирования в составе системы планирования производственных ресурсов MRPII.

1. Андреев С.А. Управление промышленными предприятиями в стандарте MRP 1. (http://cfin.ru)

2. Бакаев Н.А., Синиченко З.И., Медведев В.П. Методические вопросы технико-экономического анализа. Таганрог: ТРТИ, 1984

3. Балахонова И. Современные стандарты управления в России. Статья опубликована на сайте: http://www.e-xecutive.ru

4. Беленький П.Е. Метод системного анализа в организации производственных процессов. — М.: Экономика, 1972

5. Бухалков М.И. Внутрифирменное планирование: Учебник. — М.: ИНФРА-М, 1999

6. Гаврилов Д.А. Управление производством на базе стандарта MRP II. — СПб.: Питер, 2002

7. Генкин Б.М. Экономика и социология труда: Учебник для вузов. — М.: НОРМА—ИНФРА-М, 1999

8. Гличев А.В. Основы управления качеством продукции. — М.: АМИ, 2000

9. Де Роза К. Планирование ресурсов в зависимости от потребностей клиента (CSRP — Customer Senchreniced Resource Planning): Новый норматив для изготовителей. Перевод с англ. — М.: СОКАП, 1998

10. Дуболазов В.А. Оперативно-календарное планирование на промышленном предприятии. — С-Пб, 2000

11. Думлер С.А. Управление производством и кибернетика. М.: Машиностроение, 1969

12. Елисеев В.А. Научные основы управления промышленным предприятием.— Донецк, 1971

13. Иванов И.С., Решение задач job-shop и open-shop с помощью методов программирования в ограничениях. Тезисы докладов Конференции молодых ученых по математике, математическому моделированию и информатике, Новосибирск, 2001

14. Инновационный менеджмент: Справочное пособие / Под ред. П. Н. Зав-лина, А. К. Казанцева и JI. Э. Миндели, — СПб.: Наука, 1998

15. Исследование операций в экономике: Учеб. пособие для вузов / Под ред. Н. Ш. Кремера. — М.: Банки и биржи, ЮНИТИ, 1997

16. Калачев В.Н., Немчинов Б.В., Кривоножко В. Е. Задачи планирования в гибких производственных системах. // Автоматика и телемеханика. 1995

17. Каледина А. Лекарства будут дорогими и импортными. Отдел экономики агенства Росбизнесконсалтинг. Опубликовано на сайте www.rbc.ru

18. Калиберда Ю.Т. Основы расчета длительности производственного цикла. М.: Машиностроение, 1968

19. Карданская H.JI. Основы принятия управленческих решений: Учеб. пособие. — М.: Русская Деловая Литература, 1998

20. Каширских К. Н., Севастьянов С. В., Черных И. Д. Четырехпараметри-ческий анализ сложности задачи open shop, стр. 59-77, Дискретный анализ и исследование операций. Серия 1, 2000, том 7, № 4

21. Климов А.Н., Оленев И.Д., Соколицын С.А. Организация и планирование производства на машиностроительном предприятии. М.: Машиностроение, 1973

22. Кобринский Н.Е., Майминас Е.З., Смирнов А.Д. Экономическая кибернетика. М.: Экономика, 1982

23. Кожекин Г.Я. Организация производства: Учебное пособие.-Минск: Экоперспектива, 1998

24. Козловский В.А. Производственный и операционный менеджмент: Учебник. СПб: Специальная литература, 1998

25. Конвей Р.В., Максвелл В.Л., Миллер В.Л. Теория расписаний. М.: Наука, 197526