(I have also posted this question at stackoverflow.com because I'm not sure where it should belong.)
I have a system with the following inputs:
- Set of work items to be completed. These are variable sized. They do not have to be completed in any particular order.
- Historical data as to how long work items have taken to complete in the past. However, past performance is no guarantee of future success! That is, once we come to actually execute a work item, we may find that it takes longer or shorter than it has previously.
- There can be work items that I have never seen before and hence have no historical data about.
- Work items further have a "classification" of "parallel" or "serial".
- Set of "agents" which are capable of picking up a work item and working on it. The number of agents is fixed and known in advance. An agent can only work on one work item at a time.
- Set of "servers" against which the agents execute work items. Servers have different capabilities. Specifically, they are capable of handling different numbers of agents simultaneously.
Rules:
- If a server is being using to execute a "serial" work item, it cannot simultaneously be used to execute any other work item.
- Provided a server isn't being used to execute any "serial" work items, it can simultaneously handle as many agents as it is capable of, all executing "parallel" work items.
- There are a handful of work items which must be executed against a specific server (although any agent can do that). These work items are "parallel", if that matters. (It may be easier to ignore this rule for now!)
Requirement:
Given the inputs and rules above, I need to execute the set of work items "as quickly as possible". Since we cannot know how long a work item will take until it is complete, we cannot possibly hope to derive a perfect solution up front (I suppose), so "as quickly as possible" means not manifestly doing something stupid like just using one agent to execute each work item one by one!
Historically, I've had a very simple round-robin algorithm and simply sorted the work items by descending historical duration such that the longest running work items get scheduled sooner and, hopefully, at the end of the cycle I'm able to keep all agents and servers reasonably well loaded with short-duration work items. This has resulted in a pretty good "square" shape to the utilization graph with no long tail of long-duration work items hanging around at the end of the cycle.
This historical algorithm, however, has required me to pre-configure the number of agents and servers and pre-allocate work items to "pools" and assign pools to servers, and lots of other horrible stuff. I now need to support a dynamic number of agents and servers without having to reconfigure things. (Note that the number of servers will be fixed during a cycle - that is, the number will only change between cycles - but the number of agents may increase or decrease in the middle of the cycle.)
Once all work items are complete, we record how long each work item took to feed in to the next cycle and start again from the beginning!
