Сетевой подход для максимизации количества заданий, которые могут быть запланированы

Question

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


Дано m машин и n рабочих мест, с ограничением m≤n. Используйте алгоритм сетевого потока для решения задач по максимизации количества заданий с заданным количеством машин.

У каждой работы Ji есть время начала Si и время окончания Fi. Все машины идентичны и могут выполнять не более одной работы за раз. нам нужно найти такое назначение, чтобы мы могли запланировать максимальное количество рабочих мест.

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

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

PS: Я разработал решение с помощью жадного подхода.
Задал тот же вопрос и был сбит с отрицательным голосом без каких-либо объяснений. Следовательно, повторный вопрос, так как предыдущий вопрос не получает никакого внимания из-за отрицательных голосов.

Answer 1

Как насчет этого подхода? Я предполагаю, что вы знакомы с проблемой обращения с спросом.

Считайте, что каждое задание Ji является узлом, который имеет преимущество перед заданием Jj, если Jj можно выполнить после Ji, а Ji и Jj никоим образом не перекрываются. Теперь рассмотрим узел для каждой машины и назовите его Mi. Теперь в этой модели каждый узел Ji имеет требование -1, а каждый компьютер - 0. Также добавьте узел t с требованием n и подключите к нему каждый узел m машины с емкостью n. каждый второй край имеет емкость 1.

Теперь решите это с обращением со спросом, и я думаю, что вы получите свой ответ.