У меня есть реальная проблема, которую я пытаюсь представить и автоматизировать. Я упростил и обобщил это до следующего:
- Есть n мест работы (P1, P2, ..., Pn).
- У каждого места у Pn есть ключ, Kn.
- Есть м Рабочих, (W1, W2, ..., Wm).
- Чтобы работать в Pn, рабочий должен держать Kn.
- Каждый ключ может храниться у рабочего или оставлен на бирже E.
Работник может в любое время совершить поездку на биржу, чтобы забрать некоторые невостребованные ключи или сбросить некоторые ключи для использования другими.
Теперь существует внешний график работы, который должен быть выполнен в строгом порядке. Например:
- 2016-04-21 W1 должен работать на P6
- 2016-04-21 W2 должен работать на P3
- ** требуется обмен ключами **
- 2016-04-22 W3 должен работать на P3
- 2016-04-22 W2 должен работать на P6
Любое количество работников может работать на Pn в какой-то момент в своем графике, хотя никогда в один и тот же день
Мы знаем:
- Начальное местоположение всех ключей, либо с рабочими, либо на E
- Будущие рабочие заказы, которые каждый работник должен будет выполнить
Итак, я изо всех сил пытаюсь смоделировать всю эту ситуацию. Можете ли вы предложить структуры данных и алгоритмы, на которые мне следует обратить внимание, чтобы получить представление об этом и начать оптимизировать поездки для обмена для каждого работника?
То, что я хочу минимизировать, - это общее количество поездок в E. Вторичной целью было бы убедиться, что ни один работник не совершает непропорциональное количество поездок.
Заранее спасибо!!
источник
Ответы:
Вопрос немного двусмысленный в одном ключевом моменте: какие элементы мы пытаемся решить. Мы смотрим на оптимизацию порядка, в котором ресурсы делегируются? Минимизировать поездки на биржу? Максимизация пропускной способности заказа на работу?
Имея это в виду, я собираюсь предположить, что мы могли бы делать любую смесь из этих вещей и держать ответ на довольно высоком уровне.
Первое, что приходит мне в голову, это то, что взаимосвязанные проблемы, которые пытаются решить, в основном связаны с управлением зависимостями. Рабочие, ключи и местоположения могут рассматриваться как зависимости, которые должны быть разрешены для выполнения рабочих заданий.
Переходя к следующему уровню, я бы посмотрел на адаптацию топологической сортировки ( https://en.wikipedia.org/wiki/Topological_sorting ). Смоделируйте проблемное пространство как большой граф (современные графовые базы данных также могут быть хорошим средством для некоторых из этого анализа), а затем используйте различные топологические сортировки для решения различных аспектов проблемного пространства.
Слегка касательно, это звучит как действительно забавный проект. Сегодня я завидую вам, сэр.
источник