Тема: РЕШЕНИЕ ЗАДАЧИ МИНИМИЗАЦИИ ВЗВЕШЕННОГО КОЛИЧЕСТВА ЗАПАЗДЫВАЮЩИХ ТРЕБОВАНИЙ

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

Купить

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

Купить