title: Resource allocation algorithm for an airlock on a moon base
body: <p>I'm trying to find an algorithm or problem name on a resource allocation problem that goes something like this.</p>
  
  <p>A moon base has an airlock that only one person can use at a time, either to enter or exit, and takes 20 seconds to pass through. Airlock transitions cannot be aborted early or reversed. Astronauts have a limited amount of air when they are outside the base (say 10 minutes). Their job on the moon is to operate a number of drills that are different distances from the moon base, and keep them running with 100% manned uptime.</p>
  
  <p>I hope to answer questions like these:
  How many drill sites can be supported with no astronauts running out of air? How do you determine the schedule for the airlock (who gets to enter/exit and in what order)?</p>
  
  <p>There are 2 components:<br>
  - First figuring out the number of astronauts required to man each drill site with 100% up time.<br>
  - Figuring out the number of drills that can be operated using one airlock</p>
  
  <pre><code>Per Drill:
  MaxWorkTime[i] = AirTime - 2*TravelTime[i]
  ActualWorkTime[i] &lt; MaxWorkTime[i]
  WorkersPerDrill[i] = AirTime/ActualWorkTime[i]
  
  for each drill
    try to schedule airlock time
  </code></pre>
  
  <p>WorkTime can be reduced to schedule workers more optimally on the airlock as it approaches 100% utilization (I think).</p>
  
  <p>Below is a simple diagram to try to clarify the problem more.  The airlock time is consumed by astronauts using it and is indicated by the bars. I want to increase usage to its maximum while not sending too many astronauts outside. The astronauts work cycle is shown for one drill. The astronaut uses airlock time to exit, walks to the worksite, works, walks back to base, and uses airlock to enter.</p>
  
  <pre><code>           |---time--&gt;  
  
  Airlock:   |--x---|               |--x---|              |--x---|             |--x---|
  
  Astronaut1 |-lock-|--to--|---------drill1--------|-from-|-lock-|
  Astronaut2                        |-lock-|--to--|-------drill1--------|-from-|-lock-|
                                                  ^
                                           drill1 always manned
  </code></pre>
  
  <h2>Update (Example with numbers)</h2>
  
  <pre><code>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] &gt;= 2.5    // These numbers are over 1 airtime (10m)
  WorkersPerDrill[1] &gt;= 2
  WorkersPerDrill[2] &gt;= 1.67
  WorkersPerDrill[3] &gt;= 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
  </code></pre>
  
  <p>This is the first part of the problem. Once there is a conflict where drill[1] worker and drill[3] worker come back at the same time there is a chance one runs out of air.  That is the problem I'm trying to solve.  Thanks for putting up with this long winded question!</p>