Двухстороннее сопоставление с делимыми задачами - PullRequest
0 голосов
/ 14 сентября 2018

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

Например, у человека X есть 4 часа в день, он может выполнить 1/3 задачи A за 2 часа, 1/4 задачи B за 4 часа.Человек Y, имеющий 10 часов, может выполнить 1/5 задачи A за 1,3 часа, 1/8 задачи B за 6 часов.Есть ли расширение соответствия BiPartite, которое может решить эту проблему?

Спасибо!

1 Ответ

0 голосов
/ 14 сентября 2018

Я не думаю, что вы можете легко смоделировать это как двустороннее соответствие.Тем не менее, должно быть довольно легко создать линейную программу для вашей задачи.Просто имейте для каждого работника набор переменных x_ {i, j}, который указывает, сколько времени человека i отводится на задачу j.

Пусть h_i будет количеством часов, доступным для человека i.Тогда для каждого человека i должно быть указано, что

constraint 1

Пусть a_ {i, j} будет «эффективностью» человека i в задаче j,то есть, сколько заданий человек может выполнить за один час.Тогда для каждой задачи j она должна содержать:

constraint 2

Вот и все.Нет ограничений целостности или что-то.

...