Как возможно реализовать перебор всех работ, у которых задано время выполнения, для отыскания оптимального порядка

1). Как возможно реализовать перебор всех работ в matlab, у которых задано время выполнения, для отыскания оптимального порядка работ(наименьшее время выполнения всех работ). Работы могут выполняться параллельно только с определенными работами.

Написала алгоритм в лоб, сначала перебираю возможные разбиения параллельности работ(1 2, 1 3, 1 2 3 и тд), (проверяю из условий возможно ли эти работы выполнять параллельно). Дальше нахожу возможные перестановки. Получается не эффективно.
Думала над методом случайного поиска, не знаю как реализовать, так как паралельно можно выполнять работы по разному. Может есть мысли как можно реализовать такую работу?

2). Есть ли возможность с помощью toolbox реализовать переборные алгоритмы?

0

Anutka_, приведите условие задачи полностью. Иначе трудно сказать, какой метод лучше.

1

Дано N работ, у каждой задано время выполнения и перечень работ с которыми эту работу можно выполнять параллельно. Например:
Работа 1-время выполнения 3ч - можно выполнять параллельно с работами 2, 3.
Работа 2-время выполнения 3ч - можно выполнять параллельно с любыми работами.
Работа 3-время выполнения 2ч - выполнять параллельно можно с 1 работой
Работа 4-время выполнения 5ч - выполнять параллель нельзя - - работа должна быть выполнена после выполнения 1-ой работы.
и ТД
Нужно найти такую последовательность работ, что бы время выполнения было минимальным.

По своей сути задание подходит под методы сетевого планирования. Но мне нужно все это выполнять в автоматизированном или даже автоматическом режиме.

Для понимания:
(1 - 2) - 1 2 работы выполняются параллельно
(1-2-3)- 1 2 3 параллельно
и тд.
Тогда из приведенных условий, есть такие варианты:

(1-2)-3-4 t=10
(1-3)-2-4 t=11
(1-2)-4-3 t=10
3-(1-2)-4 t=10
(1-3)-4-2 t=11
2-(1-3)-4 t=10

(1-2-3) - так нельзя, так как в условиях сказано, 3 работа паралельно только с 1.

Тогда самый оптимальный вариант тот, где t=10 (не важно какой именно).


Это, конечно, как я понимаю задачу, может есть варианты и по другому

0

Anutka_, Похоже, что можно свести задачу вот к этому алгоритму
https://ru.wikipedia.org/wiki/Поиск_в_ширину
Графом будет вот такой набор

Сообщение от Anutka_ Тогда из приведенных условий, есть такие варианты: (1-2)-3-4 t=10 (1-3)-2-4 t=11 (1-2)-4-3 t=10 3-(1-2)-4 t=10 (1-3)-4-2 t=11 2-(1-3)-4 t=10

1

AlMih, не очень понимаю как такую задачу свести к поиску в ширину. У меня изначально нет этого графа, я как раз и должна найти возможные варианты, а найти потом какой из них оптимальный не проблема. Проблема именно найти все возможные варианты.

Добавлено через 1 минуту
Centurio, может что-нибудь теперь можете подсказать?

0

Anutka_, Надо строить матрицы связей, а по ним уже строить граф

0

Сообщение от Anutka_ Centurio, может что-нибудь теперь можете подсказать?

Могу только тоже перебор предлохить.

0