Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
45 / 45 / 5
Регистрация: 28.07.2009
Сообщений: 144
1

Рассчет времени через граф

03.05.2010, 03:07. Просмотров 543. Ответов 0
Метки нет (Все метки)

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

У меня вопрос: существует ли для подобной задачи боле-менее рациональный алгоритм (самому придумать нереал - башка уже гудит), или же тут просто перебором нужно бегать? Просто при количестве вершин порядка 10 и дуг порядка 20, это уже будут достаточно долгие расчеты... А я боюсь, что надо будет тестить более тяжелый граф.

Добавлено через 1 час 34 минуты
Ну хоть скажите, знаете ли хоть какой-то алгоритм прохода графа, у которого нагружены вершины, а не дуги???
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.05.2010, 03:07
Ответы с готовыми решениями:

Определить, сколько будет времени через заданный интервал времени
Текущее показание электронных часов: m часов, n минут и k секунд. Какое время будут показывать часы...

Нет синхронизации времени через интернет-серверы точного времени
Время на ПК отстает примерно на 30 секунд от точного времени на разных серверах. В Win7 и...

Как обойти граф, чтобы найти количество связанных компонент? Нужен оптимальный по времени алгоритм
Всем доброго вечера! Решаю задачу, никак не могу решить, чтобы проходило по времени. Поиск в...

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.05.2010, 03:07

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Снятие атрибутов с файла через определенный промежуток времени от времени запуска bat файла
Подскажите, может есть идеи как организовать такую задачу? Есть каталог с вложенными каталогами,...

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

Как преобразовать неориентированный граф в ориентированный граф из матричной записи
Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из...

Граф задан цепными списками. Построить его реберный граф
Дорогие форумчане, прошу помочь с написанием данной программы: Граф задан с помощью цепных...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.