Математическая модель задачи

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К курсовой работе

по предмету: “КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ”

На тему: Разработка программы

« Оптимизация сетевого графика по времени »

 

 

Специальность: 230105 ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ.

 

 

Выполнил

студент гр. 316-П ______________ /Щербаков Н.В./

Руководитель ______________ /Юрченко В.Н./

 

 

Щекино

2009г.

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

 

По предмету: “Компьютерное моделирование”

Студента гр. 316-П Щербакова Николая Владимировича

Специальность: 230105 Программное обеспечение вычислительной

техники и автоматизированных систем.

ТЕМА: Разработка программы «Оптимизация сетевого графика по времени»

ИСХОДНЫЕ ДАННЫЕ: карточка задания

I	J	Объем работ	Число ресурсов
0	1	25	5
0	2	30	6
0	3	20	4
1	4	22	5
2	3	10	4
2	4	15	3
2	5	5	4
3	6	25	5
4	6	20	4
5	6	5	4
6	7	30	6

 

 

Производительность рабочих = 5 ед.

Общее число задействованных в процессе производства рабочих = 50

 

ВЫХОДНЫЕ ДАННЫЕ: файл с выходными полями

Определить оптимальное время выпуска продукции.

Сформировать файл с полями: I, J, Необходимое число ресурсов, Число

ресурсов, Продолжительность, События, Резерв времени.

ВЫХОДНЫЕ ДАННЫЕ: файл с выходными полями

 

I

J

Объем работ

Не обход. ресурсов

Число ресурсов

Продолжительность

События

Резерв времени

 

ГРАФИЧЕСКАЯ ЧАСТЬ

выполнить: блок – схему программы

Главной целью является: Определить оптимальное время выпуска продукции. Усвоение методов сокращения сроков выпуска продукции путем оптимальной расстановки имеющихся трудовых ресурсов. А так же закрепление практических навыков работы с ЭВМ.

Содержание

Реферат

Ведение

1. Технические характеристики

1.1. Постановка задачи

1.1.1. Сущность задачи

1.1.2. Математическая модель задачи

1.2. Описание логической структуры

1.3. Описание и организация входных данных

1.3.1. Описание входной и выходной информации

1.3.2. Организация ведения информационной базы

1.4. Описание программных средств

1.4.1. Описание среды программирования

1.4.2. Описание программы

1.5. Описание технических средств

1.5.1. Описание и обоснование минимальной конфигурации технических средств

Заключение

Литература

Приложение A

Реферат

 

Курсовая работа по теме «Оптимизация сетевого графика по времени» выполнена в среде программирования Borland Delphi 5. Она состоит из пояснительной записки и графической части. Объем пояснительной записки составляет 35 листов формата A4, а также включает в себя 4 приложения:

· Приложение A – листинг программы;

· Приложение Б – главная форма;

· Приложение В – дополнительные окна и окно помощи;

· Приложение Г – структура меню программы.

Графическая часть представлена схемой программы, выполненной на листе формата A1.

Ключевые слова в курсовой работе:

оптимизация, работа, событие, ресурс, время, критический путь.

Введение

 

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

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

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

Технические характеристики

Постановка задачи

 

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

Задается:

· Общее количество рабочих.

· Необходимое количество изделий по каждой работе.

Производительность труда – одинаковая.

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

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

 

Сущность задачи

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

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

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

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

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

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

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

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

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

3) В отдельных случаях для ускорения выполнения критических работ могут привлекаться дополнительные ресурсы со стороны.

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

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

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

Директивный план-график рассылается ответственным исполнителям, после чего начинается выполнение комплекса работ в соответствии с разработанным графиком.

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

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

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

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

Математическая модель задачи

Для того чтобы выполнить оптимизацию сетевого графика, необходимо рассчитать и определить:

1. Необходимое число ресурсов для каждой работы:

A = B / C

где A - необходимое число ресурсов;

B - объем работ;

C – производительность.

2. Продолжительности работ:

D = A / F

где D – продолжительность работы;

A – необходимое число ресурсов;

F – число ресурсов.

3. Ранние сроки наступления событий:

t_р (j) = max {t_р (i) + t (ij)}, i<j, t_р (0) = 0

где i, j – номера событий;

t_р (i, j) – ранний срок наступления (i, j) события;

t (ij) – срок выполнения работы (i-j);

i<j – событие i предшествует j.

4. Поздние сроки наступления событий:

t_п (i) = min {t_п (j) - t (i,j)}, i<j

где i, j – номера событий;

t_п (i, j) – поздний срок наступления (i, j) события;

t (ij) – срок выполнения работы (ij);

5. Полный резерв времени для каждой работы:

R_п (i,j) = t_п (j) - t_р (i) - t (i,j)

где i, j – номера событий;

t_п (j) – поздний срок наступления события j;

t_р (i) – ранний срок наступления события i;

t (ij) – срок выполнения работы (i-j).

6. События, лежащие на критическом пути. Такие события имеют равные ранние и поздние сроки наступления.

7. Критические работы. То есть работы, у которых начальное и конечное события критические.

8. Критический путь. Рассчитывается как сумма продолжительностей критических работ.

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

 

1.2. Описание логической структуры

 

Блок-схема системы приведена на листе формата А1.

Блок 1 –начало работы;

Блок 2 – выбор из пунктов меню;

Блок 3 – выбор пункта меню файл;

Блок 4 - выбор подпункта меню “Открыть файл”;

Блок 5 – загрузка файла;

Блок 6 – выбор подпункта меню «сохранить файл»;

Блок 7 – сохранение файла

Блок 8 – выбор подпункта меню «Выход»;

Блок 9 – запрос на окончание работы;

Блок 10 – завершение работы программы;

Блок 11 – выбор меню «действие»;

Блок 12 – выбор подпункта меню «Оптимизация»;

Блок 13 –происходит оптимизация;

Блок 14 – выбор подпункта меню «прибавить строку»;

Блок 15 –прибавление строки;

Блок 16 – выбор подпункта меню «удалить строку»

Блок 17 –удаление строки;

Блок 18 - выбор пункта подменю “Очистить все”;

Блок 19 – очистка содержимого таблицы;

Блок 20 – выбор пункта меню “Помощь”;

Блок 21 – выбор из пунктов подменю;

Блок 22 – выбор подпункта меню “О задаче”

Блок 23 – открытие новой формы и вывод её на экран;

Блок 24 – выбор подпункта меню “О разработчике”

Блок 25 – открытие новой формы и вывод её на экран;

Блок 26 – выбор пункта подменю “Help”

Блок 27 – открытие новой формы и вывод её на экран;

Листинг программы приведен в Приложении “А”