我正试图找到一个算法或问题的名称在一个资源分配问题，像这样。
月球基地有一个气闸，每次只有一个人可以使用，要么进入要么退出，需要20秒才能通过。气闸转换不能提前终止或逆转。宇航员在基地外呼吸的空气是有限的(比如10分钟)。他们在月球上的工作是操作一些与月球基地距离不同的演习，并保持它们在100%的载人正常运行时间内运行。
我希望回答这样的问题:在没有宇航员耗尽空气的情况下，能支持多少个演习地点?你如何确定气闸的时间表(谁可以进入/退出，以什么顺序进入/退出)?
有两个组件:
-首先计算出在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
这是问题的第一部分。一旦发生冲突，钻[1]工人和钻[3]工人同时回来，就有可能耗尽空气。这就是我要解决的问题。谢谢你能忍受这个冗长的问题!
这甚至不是一个编程问题。更像是数学。
要让一台钻头一直保持运转，每10分钟至少需要20+20秒。那就是一个人回去，一个人出来。
你可以更频繁地换班，但这样总是效率较低。
所以，每10分钟你需要40分钟的开门时间。
然后你可以级联每个钻的位移变化，这样它们就不会重叠，如下图所示:
<- 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表示移位变化。
解决方案是10min除以40secs = 15钻
编辑:让我来猜一下细节，然后回答这个问题，以防每个站点往返基地的步行时间不同。
在这种情况下，我只是将图中的x标记分成两个半>, <分别对应一个人出去和进入。另外，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分钟。也就是说，如果你没有更好的分配方法。
在这一点上，你可能会写一个蛮力来尝试在有限的时间内分配这些标记。