2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Does the dependencies between tasks only consists in predecessor/successor relations or is it more complex? Is the number of machines fixed? What is the objective? $\endgroup$
    – fontanf
    Apr 23 at 5:30
  • $\begingroup$ Thanks, @fontanf . The dependencies don't consist of temporal relations in the form of predecessor/successor relations. Rather they affect the overall optimization objective which is to minimize some resource consumption, specifically links usage between nodes in a graph. You can think of the problem as a mix of a classical assignment and a transportation problem where I need to minimize the transportation cost. The idea is that I have a job consisting of multiple tasks needing to be scheduled concurrently with their interactions considered towards the overarching optimization objective. $\endgroup$
    – kfertakis
    Apr 23 at 11:34
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the recommendation, I will evaluate the CPOptimizer as well. However, I was wondering whether there is any greedy heuristic way to approach the problem like the network flow representation with the MinCost-MaxFlow algorithm but which takes relationships between tasks also into account. The idea is that I have a job consisting of multiple tasks needing to be scheduled concurrently with their interactions considered towards the overarching optimization objective. $\endgroup$
    – kfertakis
    Apr 23 at 12:11
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.