Тема: Оперативное планирование работы при случайном времени выполнения с учетом отказов оборудования

По мере расширения бизнеса и усиления конкуренции на рынке, большинство малых и средних предприятий испытывает необходимость в повышении эффективности производства, снижении затрат и себестоимости единицы продукции. Малое предприятие, работая в условиях определенных ограничений, может успешно функционировать в конкурентной среде в основном за счет использования внутренних резервов, выявление которых возможно только с помощью математических моделей и алгоритмов составления оптимальных расписаний и прогнозирования процесса производства. Повышение эффективности производственных процессов достигается за счет внедрения на систем оперативного управления производством, календарного планирования работ.
В нашей стране и за рубежом накоплен достаточный арсенал математических моделей и методов решения задач составления календарных расписаний, проводились многочисленные экспериментальные исследования. Тем не менее, значительная доля полученных результатов скорее выявляет сложность проблемы, чем намечает конструктивные пути ее решения. Как показали исследования, применение в реальных обслуживающих системах точных алгоритмов и даже приближенных алгоритмов с достаточно хорошими априорными оценками не представляется возможным . Таким образом, работу по реализации, математических моделей составления оптимальных расписаний в конкретных производственных условиях не следует считать завершенной.
Математические вопросы построения и анализа моделей оптимизации расписаний изучаются в рамках теории расписаний. Направление в науке берёт свое начало с известной работы Генри Гантта 1903 г, предложившего то, что сегодня называют диаграммами Гантта.
Проблемами теории расписаний занимались такие ученые, как Г. Вагнер , Д.С. Джонсон , Р.В. Конвей, В.Л. Максвелл , Т.П. Подчасова, В.С. Танаев и др. Изучаемые в теории расписаний модели отражают специфические ситуации, возникающие при календарном планировании различных видов целенаправленной человеческой деятельности. Разнообразие моделей, степень их общности и универсальности постепенно увеличивается, охватывая все более широкую сферу возможных приложений календарного планирования производства, обучения, информационно­вычислительных процессов и т. п.
Задачи составления производственных расписаний являются NP- трудными с огромной размерностью и наличием большого числа ограничений сложной формы. Одни из них достаточно специфичны, другие — сложно формализуемы. Для решения таких задач существуют три основных класса алгоритмов: эвристические, приближённые и алгоритмы сокращения перебора. Применение эвристических алгоритмов, не требующих проведения оптимизации в явном виде, позволяющих получить расписания, отвечающие требованиям.
Базовым понятием в теории расписаний является понятие работы - элементарной планируемой части процесса. Нужно составить план выполнения работ, в котором фиксируются объемы работ, моменты начала и окончания каждой работы. Понятие ресурса работ включает в себя компоненты деятельности, такие как исполнители, энергия, материалы, оборудование.
Для реализации процедур составления расписания выбран подход, комбинирующий различные алгоритмы для поставленной задачи. Он позволяет формировать решения за приемлемое время, точность которых (близость к оптимальному решению) оказывается адекватной требованиям, предъявляемым к решению. Алгоритмическая база имеет некоторые ограничения. Часть этих ограничений не имеет принципиального характера и при построении модели либо не учитывается, например наличие объемных ресурсов, либо упрощается, например время переналадки оборудования. В работе предложен адаптивный алгоритм составления расписания, в результате работы которого будет получено расписание, близкое к оптимальному. Приближённые алгоритмы гарантируют оценку качества полученного решения (погрешность), которое будет найдено за полиномиальное (от п) время. Алгоритмы сокращения перебора используются для оптимального решения NP-трудной задачи. Наиболее распространенным подклассом алгоритмов сокращения перебора являются алгоритмы, построенные по методам ветвей и границ, программирования в ограничениях, ветвей и отсечений. В каждом из этих алгоритмов происходит "разбиение" исходного примера задачи на подпримеры и существенным является нахождение эффективных нижних оценок решения подпримеров и как следствие сокращение дерева поиска.
На сегодняшний день системы автоматизированного составление производственных расписаний (APS, MES-системы) отсутствуют на большинстве малых предприятий, доминирующих в сферах инновационных разработок. Это связано с большой стоимостью и сложностью внедрения предлагаемых систем на малых предприятиях, ограниченным количеством управленческого персонала, обобщенной структурой производства, отсутствием отлаженной системы документооборота и развитой технологической базы. В сложившихся условиях возникает необходимость в разработке моделей и алгоритмов составления производственных расписаний, не требующих больших вложений при внедрении и эксплуатации, гибких и простых в применении, учитывающих специфику производства.
Классическими критериями в задачах теории расписаний являются: минимизация максимального времени окончания обслуживания (задача на быстродействие), минимизация суммарного времени окончания обслуживания, минимизация суммарного запаздывания, минимизация числа запаздывающих требований.
...
Купить

Задача оперативного управления производством, это задача составления наилучшего, с точки зрения выбранных целей и ограничений, расписания в рамках принятой модели.
В современных условиях конкуренции неоспоримым является факт огромных усилий производителей в направлении снижения себестоимости продукции. Понятно также желание производителя автоматизировать календарное планирование как долгосрочное, так и оперативное, наряду с логистикой, модернизацией производства и обучением персонала. В связи с этим была поставлена задача оперативного планирования выпуска продукции предприятием.
Анализ поставленной задачи позволяет сделать вывод о ее NP- трудности. Для решения поставленной задачи был применен модифицированный алгоритм диспетчеризации. Использование приемлемых, для задачи, эвристик позволяет получить необходимый результат, т.е. эвристические алгоритмы позволяют получить "хорошее" решение за приемлемое время, однако анализ полученного решения, в частности его численная оценка достаточно затруднительны .
При выполнении дипломной работы были получены перечисленные ниже теоретические и практические результаты.
1. Предложена методика построения системы расписания, которая опирается на два принципиальных положения:
• эффективного алгоритма, позволяющего получить оптимальное расписание за приемлемое время не существует;
• важно учитывать производственные процессы, их анализ позволяет определить применимость различных эвристик.
2. В качестве основного алгоритма был выбран однократный алгоритм диспетчеризации. Его выбор обусловлен следующими причинами:
• возможность применения комбинированных эвристик;
• получение расписания за приемлемое время.
3. Разработан ряд процедур, позволяющих реализовать построение производственного расписания указанного вида на вычислительной технике, в условиях ограниченности времени. При этом получены следующие результаты:
• описана методика построения «базового» расписания. При этом под «базовым», понимаем расписание, получаемое простым алгоритмом диспетчеризации;
• на основе базового алгоритма построена система назначения приоритетов операций, основанная на комбинации эвристик, позволяющая классифицировать ранг операции на каждом шаге итерации. Также задан итерационный процесс получения некоторого числа различных расписаний, обеспечивающий поиск локального максимума показателя качества по предложенному критерию.
4. Алгоритмическая база имеет некоторые ограничения. Часть этих ограничений не имеет принципиального характера и при построении модели либо не учитывается, например наличие объемных ресурсов, либо упрощается, например, время переналадки оборудования.
5. Эффективность работы предложенных алгоритмов проверена на ряде тестовых задач. На основе этих алгоритмов построена система составления расписания.
Купить