Scenario
Amazon Prime Now has 17-hour long days during which it deploys its fleet of trucks. The Order Forecaster for a region is really good at what they do and can give the exact number of trucks needed during each hour block for the coming day. The forecast schedule is in the form of a 17 element array. We can only deploy (add) trucks at the very beginning of the day, and any leftover trucks at the end of the day are automatically sent to maintenance. How would we algorithmically maintain a minimal service fleet? For example if the required number of trucks is forecasted as:
hour | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
#trucks | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 3 | 4 | 4 | 3 | 1 | 0 | 0 | 0 | 0 | 1 |
The optimal decommissioning schedule is:
hour | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
+/-trucks | 5 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | -1 | -2 | 0 | 0 | 0 | 0 | 0 |