Relationship aware task scheduling heuristics

Question

I have a task scheduling/assignment on machines problem (like a classic bin packing problem) with a twist in which the placement/assignment of one task affects the placement/assignment of other tasks (their placement needs to be jointly considered). I am trying to concurrently schedule the tasks and jointly consider their dependencies which can be expressed as a DAG. I have expressed the assignment problem as a MILP which is actually realized as a MIQCP in an effort to express the relations between the placements of different tasks through the constraints and minimize the number of decision variables.

However, the execution time of the optimization (CPLEX implementation) is significant, even for a really small unrealistic problem size, spanning from tens of seconds to a minute when I would ideally like to be subsecond. Two option that I am aware of is to perform the linearization of the problem, by moving from the discrete to the continuous representation, or increase the number of variables and eliminate the quadratic terms. Since this is an already proven hard problem, solving the entire MILP in practice is usually not scalable. Approaches in the past have mapped the scheduling problem into a network flow problem where a MinCost-MaxFlow heuristic algorithm is used to find the assignments (references: [1], [2]).

Instead of solving the entire MILP, the problem mapping to a network flow representation provides a heuristic greedy way to approach the assignment problem with the optimization objectives which performs much better in practice since it exploits graph properties and greedily solves the problem. However, trying to express the correlation between different tasks through the network flow representation for their concurrent scheduling and consideration, makes the option seem unfeasible. So my question is either if there is a way to track dependencies between tasks through a flow network joint scheduling approach or if any other approach exists that might map to the problem case and can meet the performance requirements of a heuristic approach.

Answer 1

since you deal with a scheduling problem I encourage you to have a look at CPOptimizer scheduling within CPLEX.

See also https://stackoverflow.com/questions/49405659/mip-vs-cp-for-scheduling-problems

Answer 2

Since you are open to a heuristic, I wonder if a restricted decision diagram (DD) might work for you. Decision diagrams are similar to dynamic programs in the sense that each node represents a state of the system and each arc represents a decision that results in a new state that is dependent only on the decision and the state at which it is made. The least cost solution is found by getting the shortest path from start node to end node. The "restricted" part is that, to avoid the size of the diagram blowing up, you glue certain nodes together (I'm pretty sure that's not the technical term for it) and/or omit certain nodes or arcs, effectively excluding some possible solutions (hopefully not the best ones). Finding the shortest path through the restricted decision diagram is a primal heuristic.

A good starting point is Willem-Jan Van Hoeve's web page on decision diagrams, which gives an overview of decision diagrams in optimization and lists various resources, including an excellent book of which he is co-author.