I'm having a problem where I have a set of precedence networks. Each networks consists of a number of nodes which have a duration, and type.
There are also a number of workers, who each have a type they can work on, which coincide with the node types.
Here is an image to clarify:
Each network also has a final deadline, which is represented with the green bar in the image.
I'm trying to assign these workers to the nodes, such that all the networks are finished as fast as possible. Also, I'm trying to finish the network before the deadline as much as possible.
I started out with some simple methods, such as: work on the nodes of the network that has the closest deadline. Or work on the nodes of the network that has the least amount time remaining when comparing the fastest possible finish time of the network, and its deadline.
These methods work in the sense that the networks are finished on time, but they are not exactly efficient.
After looking online, I saw that the critical path method is an algorithm for scheduling for these kinds of problems. I calculate the latest start and the latest finish, and calculate the slack for each node. Then I use this slack has a priority value, focussing on the nodes with the least slack.
However, this still doesn't solve the networks efficiently, as for example it focusses on the second network in the image first. Some quick messing around myself revealed that there is enough time to start on this network after all the other "Blue" nodes are finished.
The problem arises from the fact that the workers (currently one per type) are idling most of the time, since they don't have any nodes to work on yet.
What would be a good priority method to deal with such a problem? Since my use case is for hundreds of networks, each consisting of ~100 nodes, I don't believe that methods such as linear programming are feasible.
Does anyone know of a good heuristic method?
One possibility is to start with a viable schedule (say, using critical path method) and then look at a form of "neighbhorhood search" based on individual worker moves.
We look at moving a particular worker from a particular task in one network to the first available instance of that task type in another network. This implies delaying the network from which the worker is being moved and conceivably could cause some idle time for that worker if the destination task is not yet ready to go due to precedence restrictions. If the move improves overall makespan (time until the last network completes) and does not make any network run past its deadline, we accept the move. Otherwise we do not.
Potential moves can be examined in random order (make a list of all worker-task assignments, shuffle it randomly, and run through it) or maybe some specified order (earliest to latest starts?). If a run through the workers generates at least one improvement, it's probably worth another run through the list, until eventual a full pass yields no changes. I would randomize the list before each pass. Time permitting, you could generate a new starting schedule (randomly?) and repeat, always keeping the best schedule so far.
Addendum: Here are a couple of other solutions, both heuristic.
You mentioned that there is "currently" one worker per type. If, for the full size instances, there are multiple workers for each type, you could try partitioning the networks into clusters, assign one or more workers of each type to each cluster (with the restriction that they can only work on networks in their cluster), then try solving each cluster with an integer linear program.
A second option relies on the fact that if you assign a priority ordering to all tasks across all networks, it is relatively straightforward to build a schedule based on those priorities that satisfies all precedence relationships and avoids having a worker doing two things simultaneously. (I'm back to assuming one worker per task type.) The schedule built might, however, blow through individual network deadlines and is not guaranteed to have a good overall makespan. So you want to pair this with some sort of heuristic for improving the priorities. You could do this with a genetic algorithm, for instance, provided you had enough compute power to assemble individual schedules fast ("fast" being contingent, among other things, on the number of networks and tasks).