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

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

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

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

 

 

 

 

 

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

на тему:

 

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

 

 

 

Выполнила:

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

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

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

 

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

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

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

Евсеева Ю. Ю.

 

 

 

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

Оглавление

Введение……………………………………………………………………...		3
Глава 1.	Теоретические аспекты календарного планирования……	5
	1.1. Понятие календарного планирования ……………………	5
	1.2. Характеристика моделей календарного планирования….	6
	1.3. Методы решения задач календарного планирования……	7
Глава 2.	Примеры решения основных задач календарного планирования.………………………………………………….	12
	2.1. Задача Джонсона о двух станках ……………………….	12
	2.2. Задача о назначениях  ………………………...…………….	14
	2.3. Задача о замене  оборудования…………………………….	21
Заключение………………………………………………………………….		29
Литература…………………….……………………………………………		30

 

 

Введение

 

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

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

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

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

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

1. рассмотреть основы календарного планирования;
2. решить основные задачи календарного планирования.

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

 

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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