Содержание
- 2. Алгоритмы: Анализ и Построение Краткая классификация алгоритмов
- 3. Алгоритмы: Анализ и Построение Эвристические комбинаторные алгоритмы Эвристические алгоритмы дают решение хуже оптимального. Они обычно имеют
- 4. Общая постановка задачи построения расписания Алгоритмы: Анализ и Построение Существует множество различных постановок задачи построения расписаний.
- 5. Алгоритмы: Анализ и Построение Пусть, к примеру, Bi трактуются как процессорные элементы мультикомпьютера, c – объём
- 6. Алгоритмы: Анализ и Построение Можно сформулировать 3 проблемы: P1. Для фиксированного c найти минимальное число боксов
- 7. Алгоритмы: Анализ и Построение P2. Для фиксированного m найти минимальное c такое, что все pi могут
- 8. Алгоритмы: Анализ и Построение P3. Для фиксированных m и c найти максимальное n'≤n такое, что n'
- 9. Алгоритмы: Анализ и Построение Общая схема решения таких переборных задач состоит в следующем: построении множества всех
- 10. Алгоритмы: Анализ и Построение Рассмотрим сначала алгоритм построения множества всех допустимых расписаний для случая m=n. Каждое
- 11. Алгоритмы: Анализ и Построение В программировании обычно n>>m. Поэтому надо разрешать назначение на один процессор нескольких
- 12. Алгоритмы: Анализ и Построение Другое ограничение связано с учетом информационных зависимостей. Если она существует, например, между
- 13. Алгоритмы: Анализ и Построение К сожалению, добавление новых ограничений при попытке сократить множество допустимых расписаний нередко
- 14. Алгоритмы: Анализ и Построение Такие стратегии используют некоторое дополнительное знание о задаче. Рассмотрим следующий пример. Пусть
- 15. Алгоритмы: Анализ и Построение К примеру, расписание ({p1, p2, p3}, { p5, p9}, {pn-5}, …,{pn}) показывает,
- 16. Алгоритмы: Анализ и Построение Стратегия конструирования расписания должна учесть свойства задачи. Для сформулированной задачи ясно, что
- 17. Алгоритмы: Анализ и Построение Потому разумно для построения расписания использовать такую стратегию: Строятся два упорядоченных списка
- 18. Алгоритмы: Анализ и Построение Построенное расписание на практике может быть и очень хорошим и не очень,
- 19. Алгоритмы: Анализ и Построение Это практически полезная стратегия, которая позволяет строить приемлемые расписания. Её часто применяют
- 20. Алгоритмы: Анализ и Построение Построение расписания работы домостроительного комбината
- 21. Библиотека фрагментов
- 22. Библиотека фрагментов
- 23. Библиотека фрагментов
- 24. Библиотека фрагментов
- 25. Библиотека фрагментов
- 26. Библиотека фрагментов
- 29. Ещё один способ построения эвристического алгоритма и способ сокращения перебора ДАНО Множество бригад b1, b2, …
- 30. Алгоритмы: Анализ и Построение b2, dj5,T2j5 b1, dj2, k2,T1j2 b1, dj3,k3, T1j3 b1, dj4,k4, T1j4 b1
- 31. Алгоритмы: Анализ и Построение Одновременно используются разные краны Время считается в днях. Дата Tij = Tij
- 32. Алгоритмы: Анализ и Построение Алгоритм формирования расписания Очередное назначение. Начинает строиться, когда появляется хотя бы одна
- 33. Алгоритмы: Анализ и Построение 2. Затем делается первое назначение всех бригад. 3. Затем делается второе назначение
- 34. Алгоритмы: Анализ и Построение Сокращение перебора, удовлетворение внесистемных требований. Добавление ограничений/требований Например, потребовать, чтобы некоторый конкретный
- 36. Скачать презентацию