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: , ).
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.