Валерий Костенко / Евгений Кочерга (3-й курс) opt-sem

На этом форуме публикуются и уточняются постановки задач студентам, а также отслеживается ход их выполнения

Модератор: staff

Закрыто
Бычков Иван
Аспирант
Сообщения: 179
Зарегистрирован: 23 сен 2008 01:19 pm

Валерий Костенко / Евгений Кочерга (3-й курс) opt-sem

Сообщение Бычков Иван »

Задачи и алгоритмы построения многостадийных расписаний.

Задача построения многостадийных расписаний заключается в следующем: задано N требований, которые должны быть обслужены последовательно M приборами. Каждое требование обслуживается сначала прибором 1, затем прибором 2 и т.д., наконец прибором М. Требуется построить расписание выполнения требований, такое, что время выполнения его минимально. Для каждого требования задано время его обслуживания приборами (в общем случае может задаваться также и порядок обслуживания требования приборами). Каждый прибор обслуживает одновременно не более одного требования. Время начала обслуживания прибором очередного требования определяется или временем завершения обслуживания этого требования предшествующим прибором или временем завершения предыдущего требования этим прибором. Прерывания обслуживания требований прибором не допускаются.
Задача построения многостадийных расписаний возникает при планировании технологических процессов в химической, фармацевтической и пищевой промышленности. При М>2 данная задача решается с использованием специализированных эвристических алгоритмов. Специализация алгоритмов заключается в том, что они ориентированы на решения частных задач, т.е. задач в которых накладываются дополнительные ограничения на заданный набор требований. Например, время обслуживания i-м прибором для всех требований одинаково.
Студент на третьем курсе должен будет выполнить следующую работу:
1. Рассмотреть известные частные задачи построения многостадийных расписаний и алгоритмы их решения.
2. Сделать формальную постановку частной задачи построения многостадийных расписаний на основе данных о технологическом процессе, полученных от группы компаний занимающихся, экстрагированием многоассортиментного растительного сырья.
3. Провести анализ задачи с целью возможности использования (критерии точность и вычислительная сложность) известных алгоритмов. Если таких алгоритмов не окажется, то предложить принципы построения специализированного алгоритма для решения этой задачи.
4. Практическая часть будет заключаться: в реализации алгоритма полного перебора для построения многостадийных расписаний и графического интерфейса для ввода исходных данных и отображения расписаний. Алгоритм полного перебора может быть построен по различным схемам существенно отличающихся друг от друга по вычислительной сложности. Это связано со спецификой вычисления времени выполнения расписаний. Кроме того, возникает дополнительное требование к алгоритму возможность эффективного распараллеливания. Это требование обусловлено тем, что в случае небольших значений N и М параллельный алгоритм полного перебора приемлем по вычислительной сложности для решения практических задач.
Закрыто