tag:blogger.com,1999:blog-593563533834706486.post7071873603461013235..comments2024-03-28T10:35:10.453-04:00Comments on Yet Another Math Programming Consultant: Assigning jobs to machines without overlapErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-593563533834706486.post-15134773379301480892023-03-17T10:37:13.762-04:002023-03-17T10:37:13.762-04:00Sorry, I see your old comment is marked as spam an...Sorry, I see your old comment is marked as spam and hidden (don't know why; must be AI). Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-50959692890048978492023-03-17T10:06:53.425-04:002023-03-17T10:06:53.425-04:00It worked well for me, and I look forward to seein...It worked well for me, and I look forward to seeing your update. By the way, my original comment somehow got deleted.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-55393971870874858482023-03-17T06:57:59.335-04:002023-03-17T06:57:59.335-04:00I need to try that!I need to try that!Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-42295747213426653132023-03-16T15:34:14.898-04:002023-03-16T15:34:14.898-04:00In fact, because the graph is an interval graph (h...In fact, because the graph is an interval graph (https://en.wikipedia.org/wiki/Interval_graph), you can solve the node coloring problem via minimum-cost network flow on a directed network, without explicitly using integer variables. For this instance, the network has 264 nodes and 8158 arcs. The objective is to minimize the flow from the source node to the job nodes. See my answer here: https://math.stackexchange.com/questions/4653921/scheduling-jobs-with-fixed-start-and-end-time-on-limited-machines/4654550#4654550Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-19078404972966558772023-03-08T13:31:17.568-05:002023-03-08T13:31:17.568-05:00In fact, because the graph is an interval graph, y...In fact, because the graph is an interval graph, you can solve the node coloring problem via minimum-cost network flow on a directed network. For this instance, the network has 264 nodes and 8158 arcs. The objective is to minimize the flow from the source node to the job nodes. See my answer here: https://math.stackexchange.com/questions/4653921/scheduling-jobs-with-fixed-start-and-end-time-on-limited-machines/4654550#4654550Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-14048041793424415582023-02-27T13:37:06.668-05:002023-02-27T13:37:06.668-05:00The GANTT chart would be largely the same (differe...The GANTT chart would be largely the same (different numbers and even more colors). The CSV file already contains the subjob ids (column k). Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-31939900874966472532023-02-27T12:45:35.919-05:002023-02-27T12:45:35.919-05:00Amazing work Erwin! Question, how would the graph ...Amazing work Erwin! Question, how would the graph output a table of what subjobs each machine would run?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-52408150279405776592023-02-20T14:53:18.826-05:002023-02-20T14:53:18.826-05:00I had the same idea as Rob Pratt: this is a graph ...I had the same idea as Rob Pratt: this is a graph theory problem. Interesting that the MIP solved so quickly despite the symmetry in the use[m] variables.Greg Glocknerhttps://www.gurobi.comnoreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-79136695968302842292023-02-17T03:29:13.734-05:002023-02-17T03:29:13.734-05:00networkx has a coloring heuristic. I need to try t...networkx has a coloring heuristic. I need to try this out!Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-78436835218292869162023-02-16T12:24:57.985-05:002023-02-16T12:24:57.985-05:00You can think of this as a graph coloring problem ...You can think of this as a graph coloring problem in a graph with one node per job, one edge per overlapping pair of jobs, and one color per machine. You want to minimize the number of colors used subject to each node getting exactly one color and no edge having nodes of the same color.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.com