Введение 3
1. Цель работы 5
2. Постановка задачи минимизации взвешенного количества
запаздывающих требований 6
3. Алгоритм решения задачи 8
4. Программная среда 9
5. Программирование алгоритма задачи 12
6. Программирование генерации чисел 13
7. Использование проекта 14
8. Анализ применимости задачи минимизации взвешенного количества
запаздывающих требований 16
Заключение 22
Литература 23
Приложение
Во время всей нашей жизни мы составляем множество расписаний: расписания ждут нас в университете, школе, есть расписания транспортных средств, программ телепередач. Те, расписания, которые мы составляем для решения бытовых вопросов, не вызывают у нас сложностей. Главное - чтобы расписание было оптимальным для решения нашей проблемы.
Наш мир в постоянном развитии, и теперь уже нужно составлять алгоритмы расписаний, чтоб решить большие проблемы. Сложности в составлении расписания возникают, когда дел становится очень много, но при этом у каждого дела есть свое дополнительное условие или, к примеру, нужно составить расписание для множества человек со множеством работ.
Со временем для таких расписаний начали придумывать методы и алгоритмы решений, так и зародился раздел науки - Теория Расписаний. Сам термин «теория расписаний» предложил Р. Беллман в 1956 году.
Теория расписаний - это раздел исследования операций, в котором анализируются и строятся математические модели календарного планирования (то есть упорядочиваются по времени) различных целенаправленных действий с учетом целевой функции и различных ограничений [1, С.23].
Где возникают задачи составления расписаний:
• При планировании занятий в школах, университетах, студиях
• На транспортных предприятиях, при составлении расписаний движений поездов, самолетов, маршруток, кораблей
• В государственных учреждениях, к примеру, в медицине составляют расписание дежурств врачей
• На производстве, когда нужно упорядочить отдельные операции по исполнителям и по времени.
• На спортивных мероприятиях
• На военных операциях
Задача теории расписаний - задача оптимизации процесса обслуживания конечного множества требований в системе, содержащий конечное количество приборов.
Классификация задач теории расписаний:
• Задачи с прерываниями и без прерываний.
• Количество обслуживающих приборов:
Одного прибора или многих приборов.
• Наличие стадий в обслуживании требований: Одностадийные или многостадийные.
• Порядок прохождения приборов:
Для многостадийных многоприборных задач:
Job shop - фиксированный, но разный для разных требований.
Open shop - нефиксированный порядок.
Flow shop - фиксированный, заданный для всех требований.
• Критерий оптимальности:
Критерий максимального штрафа, критерий суммарного штрафа.
Вопрос составления эффективных и оптимальных по времени алгоритмов расписаний остается по-прежнему актуальным, так как решения некоторых трудоёмких задач связаны с большими временными затратами.
Свойства оптимальных расписаний и эффективные алгоритмы решения некоторых NP - трудных задач теории расписаний для одного прибора рассматривались в работе [2, С. 23].
В данной работе были поставлена цель - исследовать решение задачи минимизации взвешенного количества запаздывающих требований. В ходе работы были изучены задачи теории расписаний, был выбран оптимальный язык программирования среди других для реализации задачи, был написан алгоритм задачи минимизации взвешенного количества запаздывающих требований, а также исследована его применимость на примерах различной размерности. В результате мы получили коэффициент в процентном соотношении, для скольких задач алгоритм применим, для скольких - нет. В ходе работы над дипломной работой были достигнуты поставленные цели и задачи.
Немаловажную роль играло и скорость выполнения алгоритма. В наше время каждый руководитель организации стремиться сократить сроки выполнения и обслуживания приборов, чтобы выиграть время, поэтому задачи планирования очень актуальны в наше время.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
