#algorithm
#алгоритм
Вопрос:
Я пытаюсь найти алгоритм или название проблемы для проблемы распределения ресурсов, которая выглядит примерно так.
На лунной базе есть воздушный шлюз, которым одновременно может воспользоваться только один человек, либо для входа, либо для выхода, и прохождение через который занимает 20 секунд. Переходы воздушного шлюза нельзя прервать досрочно или обратить вспять. У астронавтов есть ограниченное количество воздуха, когда они находятся за пределами базы (скажем, 10 минут). Их работа на Луне заключается в проведении нескольких учений, находящихся на разных расстояниях от лунной базы, и поддержании их бесперебойной работы со 100% персоналом.
Я надеюсь ответить на вопросы, подобные этим: Сколько буровых площадок можно поддерживать без того, чтобы у астронавтов заканчивался воздух? Как вы определяете расписание для шлюза (кто входит / выходит и в каком порядке)?
Есть 2 компонента:
— Сначала вычисляется количество астронавтов, необходимое для укомплектования каждой буровой площадки со 100% временем готовности.
— Вычисление количества тренировок, которые могут выполняться с использованием одного шлюза
Per Drill:
MaxWorkTime[i] = AirTime - 2*TravelTime[i]
ActualWorkTime[i] < MaxWorkTime[i]
WorkersPerDrill[i] = AirTime/ActualWorkTime[i]
for each drill
try to schedule airlock time
Рабочее время может быть сокращено, чтобы более оптимально распределить работников на шлюзе по мере приближения к 100% загрузке (я думаю).
Ниже приведена простая диаграмма, чтобы попытаться прояснить проблему больше. Время шлюзования затрачивается использующими его астронавтами и обозначается столбиками. Я хочу увеличить использование до максимума, не отправляя слишком много астронавтов наружу. Рабочий цикл астронавтов показан для одного упражнения. Астронавт использует время шлюза для выхода, идет к месту работы, работает, возвращается на базу и использует шлюз для входа.
|---time-->
Airlock: |--x---| |--x---| |--x---| |--x---|
Astronaut1 |-lock-|--to--|---------drill1--------|-from-|-lock-|
Astronaut2 |-lock-|--to--|-------drill1--------|-from-|-lock-|
^
drill1 always manned
Обновление (пример с числами)
AirTime = 10min
WalkSpeed = 1 m/s
drill[0] = 180m // 6min to/from travel
drill[1] = 150m // 5min
drill[2] = 120m // 4min
drill[3] = 240m // 8min
TravelTime[0] = 6min
...
MaxWorkTime[0] = AirTime - TravelTime[0] = 4min
...
// WorkersPerDrill = AirTime/MaxWorkTime
WorkersPerDrill[0] >= 2.5 // These numbers are over 1 airtime (10m)
WorkersPerDrill[1] >= 2
WorkersPerDrill[2] >= 1.67
WorkersPerDrill[3] >= 5
TotalWorkersPerAirtime = sum(WorkersPerDrill) = 11.17
AirlockTime = 20s
AirlockPerWorker = 40s
TotalAirlockUsage = TotalWorkersPerAirtime*AirlockPerWorker = 7.4 min of airlock time
74% usage of airlock if no one uses it at the same time
Это первая часть проблемы. Как только возникает конфликт, при котором рабочие drill [1] и drill [3] возвращаются одновременно, есть вероятность, что у одного из них закончится воздух. Это проблема, которую я пытаюсь решить. Спасибо, что ответили на этот затянутый вопрос!
Комментарии:
1. Не могли бы вы убедиться, что ваш код правильно отформатирован? Кроме того, это домашнее задание?
2. Это не домашнее задание. Мне не нужно решение, просто название проблемы / алгоритма, который я могу начать исследовать, чтобы лучше понять его. Теперь диаграмма имеет смысл?
Ответ №1:
Это даже не проблема программирования. Больше похоже на простую математику.
Чтобы одна дрель работала постоянно, вам нужно тратить по крайней мере 20 20 секунд каждые 10 минут. Это для того, чтобы один парень вернулся, а другой вышел.
Вы можете менять смены чаще, но это всегда менее эффективно.
Итак, вам требуется 40 секунд на открытие двери в течение 10 минут для тренировки.
Затем вы можете каскадировать смену каждого упражнения, чтобы они не перекрывались, как показано на диаграмме ниже:
<- 10 mins ->
drill-1 x--------------x--------------x--------------x
drill-2 -x--------------x--------------x--------------
drill-3 --x--------------x--------------x-------------
...
drill-15 --------------x--------------x--------------x-
Где ширина каждого символа на диаграмме равна 40 секундам времени и x
представляет смену смены.
тогда решение занимает 10 минут, разделенных на 40 секунд = 15 упражнений
РЕДАКТИРОВАТЬ: Позвольте мне просто угадать детали и ответить на вопрос на случай, если у каждого сайта разное время в пути до базы и обратно.
В этом случае я просто разделяю x
отметку на диаграмме на 2 половины >
, <
соответствующие парню, выходящему и входящему соответственно. Дополнительно должны w
представлять фиксированное время прохождения туда и обратно для каждой тренировки.
Также ясно, о каком упражнении мы говорим, всегда сначала выбирайте ближайшие упражнения.
Диаграмма становится (не масштабируемой):
drill-1 >w<-------------->w<-------------->w<-------------->w<
drill-2 ->ww<------------->ww<------------->ww<------------->w
drill-3 -->ww<------------->ww<------------->ww<------------->
drill-3 --->www<------------>www<------------>www<------------
...
Где ограничение заключается в том, что никакие метки >
или <
не могут перекрываться.
Однако вы можете просто представить распределение в виде одного 10-минутного фрагмента. Поскольку диаграмма всегда будет иметь повторяющийся период в 10 минут.
Почему? потому что, если какая-либо из диаграмм детализации будет повторяться более 10 минут, какой-нибудь астронавт погибнет. И если период выполнения какого-либо упражнения составляет менее 10 минут, вы можете просто позволить астронавту осмотреть достопримечательности, чтобы продлить период до 10. То есть, если у вас нет лучшего распределения, чтобы сделать.
На этом этапе вы, вероятно, могли бы написать грубую силу, чтобы попытаться распределить эти метки только за этот ограниченный период времени.
ПРАВКА 2: Я думаю, что в моих рассуждениях может быть ошибка, почему достаточно ограничить период всего 10 минутами.
Комментарии:
1. В простейшей форме, когда все буровые площадки одинаково удалены от базы, это будет работать так, как вы предлагаете. Как вы решаете проблему, если все буровые площадки находятся на разном расстоянии?
2. Что ж, тогда вам лучше описать в вопросе, как расстояние влияет на время, необходимое для начала добычи!
3. И я не имею в виду описывать это как «… ходит на рабочее место, работает, возвращается на базу …», как вы уже делали. Я имею в виду, опишите, какой информацией вы располагаете, которая помогает рассчитать время, необходимое для перехода к каждому месту? есть ли у вас скорость ходьбы астронавта? у вас есть карта всей зоны добычи? все ли сайты имеют одинаковое расстояние до базы? все ли астронавты ходят с одинаковой скоростью? Кроме того, должен ли астронавт проходить через лабиринт астероидного поля и сражаться с инопланетянами перед добычей полезных ископаемых? ;P
4. @user3799626 Извините, я считаю, что мой расширенный ответ по-прежнему содержит недостаток. Но у меня больше нет времени тратить на это.
5. Я действительно ценю вашу помощь. Это немного сложно объяснить, но в основном требуется больше рабочих для более удаленных точек. Время возвращения домой со временем не синхронизируется, и шлюз может заблокировать кого-то.