Календарное планирование

Федеральное агентство по образованию РФ

Государственное образовательное учреждение высшего профессионального образования

«Владимирский государственный гуманитарный университет»

КУРСОВАЯ РАБОТА

на тему:

«Календарное планирование»

Выполнила:

студентка группы ММ-31

очной формы обучения ТЭФ

Дементьева Дарья Александровна

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

                    доцент кафедры

алгебры и теории чисел

Евсеева Ю. Ю.

Владимир, 2010 г.

Оглавление

Введение

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

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

Предметом исследования курсовой работы является экономико-математическое моделирование. Объектом исследования – календарное планирование.

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

Указанная цель обусловила постановку и решение следующих задач:

а)               рассмотреть основы календарного планирования;

б)               решить основные задачи календарного планирования.

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

Глава 1. Теоретические аспекты календарного планирования

1.1 .  Понятие календарного планирования

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

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

Основными параметрами календарных графиков являются[1]: приоритетность работ (очередность запуска изделий в обработку), размер партий запуска и время опережения начала обработки изделий на связанных рабочих местах, размер незавершенного производст­ва. Результатом составления оптимального календар­ного графика является определение наименьшей длительности производственного цикла, оказывающей существенное влияние на улучшение экономических результатов деятельности предприятия. В этом случае происходит снижение объема оборотных средств в незавершенном производстве, уменьшаются простои оборудования и рабочих.

В производственных подразделениях машино­строительных предприятий календарное планирова­ние в настоящее время основано главным образом на моделировании, позволяющем обеспечить пропор­циональность, непрерывность, устранить «узкие мес­та» и правильно установить приоритеты работ. Сле­дует отметить, что установление очередности запуска изделий в производство является одной из основных задач, которую необходимо решить при составлении оптимального календарного графика.

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

1.2 Характеристика моделей календарного планирования

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

К системообразующим элементам[2] модели календарного планирования относятся:

- конечное множество частично взаимосвязанных операций G={gj}, j=1, 2, …, J;

- конечное множество работ (заданий, проектов) Р ={pi},  , i = 1, 2,…, I,  представляющих собой подмножества операций  не связанных отношением предшествования (т.е. никакие две операции, принадлежащие разным подмножествам G1 и G2, не связаны отношением предшествования);

-  конечное множество видов ресурсов R ={rk},  , k = 1, 2,…, K,   где К — определяет общее количество видов ресурсов, различаемых по своим характеристикам;

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

• моменты начала и окончания выполнения каждой операции из множества G: αi,j,k и  β i,j,k соответственно, которые всегда являются неизвестными модели.

1.3 Методы решения задач календарного планирования

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

Точные методы.

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

Метод линейного программирования удачно ис­пользован С.М. Джонсоном для решения задачи на­хождения оптимального по календарному времени плана обработки m деталей на двух станках. Алго­ритм Джонсона чрезвычайно прост. Выбирается са­мое короткое операционное время, и если оно отно­сится к первому станку, планируют выполнение зада­ния первым на первом станке, а если ко второму - то последним. Затем процедура повторяется до полного перебора всех заданий на обоих станках. Имеются многочисленные обобщения правила Джонсона для различных случаев трехстадийной обработки деталей. Однако этот алгоритм неприменим для случаев обра­ботки деталей на большем количестве станков.

Метод динамического программирования удачно использован Р. Беллманом для однооперационного производства. Он дал частное решение задачи опти­мального календарного планирования обработки со­вокупности изделий, имеющих одинаковый процесс производства, но различных по длительности опера­ций обработки. Запуск изделий в производство необ­ходимо осуществлять, соблюдая условие: min (t11, t22) < min (t12, t21), где: t11 - трудоемкость выполнения первой операции над изделием, первым запускаем в производство; t22 - трудоемкость выполнения вто­рой операции над изделием, вторым запускаем в про­изводство, а t12 и t2l - соответственно наоборот.

Метод «ветвей и границ», являющийся комбина­торным методом дискретного программирования, предполагает уменьшение множества допустимых решений, вплоть до получения конечного множества, при котором оказывается возможным применение метода перебора. В этом методе происходит последо­вательный выбор пары номеров деталей для получе­ния оптимальной последовательности. Составление последовательности номеров деталей для запуска в производство происходит в процессе работы итерационного алгоритма. На каждой итерации выбираются две детали и помещаются на позиции: (n + 1) и (d – n), где n - номер итерации, a d- количество наименова­ний деталей, участвующих в производственном про­цессе. Эффективность метода «ветвей и границ» зави­сит от уровня, на котором происходит «отсечение» ветви. В общем случае этот метод не исключает пол­ный перебор всех возможных вариантов.

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

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

Приближенные методы.

К числу приближенных методов[4] оптимизации задач календарного планирования относятся: частич­ный и направленный перебор, метод Монте-Карло, аналитико-приоритетные, эвристические и др. мето­ды.

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

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