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

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

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