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

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

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

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

 

 

 

 

 

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

на тему:

 

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

 

 

 

Выполнила:

студентка группы ММ-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- количество наименований деталей, участвующих в производственном процессе. Эффективность метода «ветвей и границ» зависит от уровня, на котором происходит «отсечение» ветви. В общем случае этот метод не исключает полный перебор всех возможных вариантов.

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

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

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

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

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

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

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

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

Глава 2. Примеры решения основных задач календарного планирования

 

2.1 Задача Джонсона  о двух станках⁵

Рассмотрим задачу последовательной обработки на двух машинах N различных  деталей, если известно время Ai и Bi обработки i -й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.

Если обозначить через Xi - время простоя в ожидании i - й детали, то

X₁=A₁;

X₁+X₂=max(A₁+A₂-B₁,A₁)

X₁+X₂ +X₃= max(A₁+A₂+A₃-B₁-B₂, A₁+A₂-B₁ A₁),…

Если обозначить через F(t, A_k, B_k/k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:

F(t, A_k, B_k/k=1..N)=min[A_i +F(B_i + max(t-A_i,0), A_k, B_k/k=1..N, k≠i

Если после i - й детали при оптимальном порядке обрабатывается j-я, то

 F(t, A_k, B_k/k=1..N)= A_i+ A_j+F(t_ij, A_k, B_k/k=1..N; k≠i, j), где

t_ij= B_j + max[B_i + max(t-A_i,0)- A_j,0]= B_j + B_i – A_j – A_i +max [t, max(A_i+ A_j - B_i,A_i]

При обработке в обратном порядке 

F(t, A_k, B_k/k=1..N)= A_j + A_i+ F(t_ij, A_k, B_k/k=1..N; k≠i, j), где

t_ji= B_i max[B_i + max(t-A_j,0)- A_i,0]= B_ji+ B_j - A_i - A_j +max [t, max(A_j+ A_i – B_j,A_i]

Если max(A_i+ A_j - B_i,A_i)< max(A_j+ A_i – B_j,A_i), то сначала разумнее обрабатывать j - ю деталь.

Можно показать, что указанное  условие необходимости перестановки эквивалентно условию 

min(A_j, B_i)< min(A_i, B_j)

Соответственно ищем среди всех значений A_i и B_i наименьшее. Если найденное значение совпадает с некоторым A_i, то i - ю деталь ставим на обработку первой; если оно совпадает с некоторым B_i, то последней. Эту процедуру повторяем для всех остальных деталей.

Пример. Пусть информация о времени обработки задана таблицей 1

Таблица 1

Время обработки деталей

i	1	2	3	4	5	6	7	8
Ai	4	4	30	6	2	9	13	9
Bi	5	1	4	30	3	13	9	9

 

Минимальное из значений равно 1 и соответствует B₂: вторая деталь обрабатывается последней. Минимальное из значений (кроме второго столбца) соответствует A₅: пятая деталь обрабатывается первой. Минимальное из значений в столбцах, кроме 2 и 5, равно A₁ и соответственно среди рассмотренных сейчас деталей эта деталь обрабатывается первой и т.д. В итоге упорядоченная информация принимает вид (таблица 2):

Таблица 2

Упорядоченная информация

I	5	1	4	8	6	7	3	2
Ai	2	4	6	9	9	13	30	4
Bi	3	5	30	9	13	9	4	1

 

Время простоя второй машины при  первичном порядке равно 

max(4,4+4-5,4+4+30-5-1,4+4+30+6-5-1-4,4+4+30+6+2-5-1-4-30,4+4+30+6+2+9-5-1-4-30-3,4+4+30+6+2+9+13-5-1-4-30-3-13,4+4+30+6+2+9+13-5-1-4-30-3-13)=max(4, 3, 32, 34, 6, 12, 12, 12)=34

Время простоя при  оптимальной перестановке равно 

max(2,2+4-3,2+4+6-3-5,2+4+6+9-3-5-30,2+4+6+9+9-3-5-30-9,2+4+6+9+9+13-3-5-30-9-13,2+4+6+9+9+13+30-3-5-30-9-13-9,2+4+6+9+9+13+30+4-3-5-30-9-13-9-4)=max(2, 3, 4, -17, -17, -17, 4, 4)=4

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

 

2.2 Задача о назначениях⁶

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

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

Таблица 3

Случаи применения задачи

Ресурсы	Объекты	Критерии эффективности
Рабочие Грузовые автомобили Станки Экипажи коммивояжер	Рабочие места Маршруты Участки Рейсы города	Время Затраты Объем переработанной продукции Время простоя товарооборот

Матрица стоимостей назначения С определяется как: С=С(с_ij), где с_ij, i, j = 1,2,…,n – затраты, связанные с назначение i-го ресурса на j-й объект, n- число объектов или ресурсов.

Положим x_ij=1, если i-й ресурс назначается на j-й объект, и x_ij=0 в противном случае. Тогда решение задачи о назначении может быть записано в виде матрицы Х=(x_ij)_n*n.

Допустимое решение  задачи называется назначением. Оно  находится путем такого выбора элементов x_ij матрицы Х, что в каждой строке и в каждом столбце будет только один выбранный элемент. Элементы с_ij матрицы С, соответствующие выбранным элементам x_ij=1 матрицы Х, отметим кружками.

Например,

                  4          7         0

С=(с_ij)=     0          3         8

                            6          0         9

Тогда решение задачи о назначениях имеет вид:

      

 

 

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

             _{n   n}

L(X) = ∑∑c_ijx_ij→min

           ^{i=1 j=1}

                                 _n

при ограничениях ∑x_ij=1, i=1,2,….n

                               ^j=1

                                _n

                               ∑x_ij=1, j=1,2,….n

                               ⁱ⁼¹

                              x_ij=0 или 1.

Задача о назначениях  является частным случаем транспортной задачи, в которой а_i=b_j=1. поэтому задачу о назначениях можно решать с помощью алгоритмов, предназначенных для транспортной задачи. Однако есть и другой метод, который более эффективен, так как он учитывает специфику математической модели. Этот метод называют венгерским алгоритмом. Он состоит из следующих шагов:

1. проведение преобразования строк и столбцов матрицы С;
2. определения назначения;
3. модификация преобразования матрицы.

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

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

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

Если после проведения 3-го шага оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех  пор, пока не будет получено допустимое решение.

Пример. Дана матрица ресурсов

 

С=(с_ij)=

 

 

Распределить ресурсы  матрицы С по четырем объектам.

Решение. 1-й шаг. Значение минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим матрицу вида

 

 

 

Значения минимальных элементов  столбцов 1, 2, 3 и 4 равны 5, 0, 0, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим:

2-й шаг. Ни одно  назначение не получено, необходимо  провести модификацию матрицы  стоимостей.

3-й шаг. Вычеркиваем столбец 1, строку 3, строку или столбец 2. значение минимального невычеркнутого элемента равно 2:

 

 

 

 

Вычитаем его из всех невычеркнутых  элементов и, складывая его со всеми элементами, расположенными на пересечении двух линий, получим:

 

 

 

Следовательно, оптимальное решение:

 

          Х_опт =

 

Таким образом, первый ресурс направляем на 3-й объект, второй – 2-й  объект, третий ресурс – на 4-й объект, четвертый – на 1-ый объект. Стоимость  назначения: 9+4+11+4=28.

Примечания:

1) Если исходная матрица  не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2) Если какой-либо ресурс  не может быть назначен на  какой-то объект, то соответствующая  стоимость полагается равной  достаточно большому числу М.

3) Если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на -1 и сложить с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем следует решать задачу минимизации целевой функции.

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

Пример:

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

 

 

 

 

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

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

 

 

 

Минимальные элементы в строках  равны 3, 4, 4, 6, 4. вычтем их из соответствующих  элементов матрицы:

 

 

 

 

 

 

 

Так как назначение не получено, вычеркиваем  строку 2, столбы 2, 4, 5:

 

 

 

 

Минимальный элемент равен 1. вычитаем его из всех невычеркнутых элементов  и складываем со всеми элементами, расположенными на пересечении двух линий, получаем:

 

 

 

 

Оптимальное решение, соответствующее  последней матрице:

 

 

 

 

Суммарная производительность: 6+6+3+6+7=28

Таким образом, наибольшая суммарная производительность станков  цеха будет равна 28 деталям в единицу  времени, при этом за первым станком  надо закрепить 5-ю операцию, за вторым – 1-ю операцию, за третьим – 4-ю  операцию, за четвертым – 3-ю операцию, за пятым станком – 2-ю операцию.