4 ms·

I'm surprised that nobody talked about the problems of scheduling problem, being NP-Complete, is all about finding heuristics to workaround this ultimate algori

by stevefan1999 3y ago

I'm surprised that nobody talked about the problems of scheduling problem, being NP-Complete, is all about finding heuristics to workaround this ultimate algorithmic hard truth. And for multicore scheduling, job shop scheduling [1], it is the even harder version of NP-Hard (no pun intended). This is literally taught in senior year uni CS class, that there is no perfect solution to the scheduling problem, unless Cook-Levin Theorem or anyone of those NP-Complete problems are solved [2]. [1]: https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling https://optimization.cbe.cornell.edu/index.php?title=Job_sho... [2]: https://www.cse.cuhk.edu.hk/~siuon/csci3130-f19/slides/lec22.pdf https://www.cse.cuhk.edu.hk/~siuon/csci3130-f19/slides/lec22...

mochomocha 3y ago
This is technically true but practically irrelevant. Case in point, I deployed at Netflix a real-time combinatorial solver specifically for CPU scheduling [1]. Most real-world combinatorial problems can be solved relatively well. This is why Gurobi is in business, Alpha Go exists, or why Amazon and United Airlines still manage to practically solve their resource allocation problems. [1]: https://netflixtechblog.com/predictive-cpu-isolation-of-containers-at-netflix-91f014d856c7 https://netflixtechblog.com/predictive-cpu-isolation-of-cont...
- skyde 3y ago
  first time earing about Gurobi, is it some kind of SMT solver? I tried looking at their website but could only find high level marketing description.