News for hackers. Stuff that matters.
Re:American Airlines Accidentally Let Too Many Pilots Take t... by mlevental on Wednesday November 29, 2017 @11:20PM (#15813448)
clrs has plenty on it.
Re:American Airlines Accidentally Let Too Many Pilots Take t... by applecrazy on Wednesday November 29, 2017 @11:44PM (#15813530)
thanks, but I was looking for the specific name of the algorithm. I don't even know what to call it, a dependency graph solving algorithm or something?
Re:American Airlines Accidentally Let Too Many Pilots Take t... by mmillin on Thursday November 30, 2017 @07:18AM (#15815144)
A basic start would be looking at network flow problems. While they don't extend to the complexity of real world airline scheduling, you can construct a simplified airline scheduling problem with it. Additionally, one of the methods to solve these problems, linear programming, does extend to integer linear programming which can be used to solve the more complicated cases (in non-deterministic polynomial time).
Re:American Airlines Accidentally Let Too Many Pilots Take t... by ddinh on Thursday November 30, 2017 @01:18AM (#15813861)
I imagine you could encode the problem as a CSP with each of the legal/contractual factors as a constraint. Despite NP-hardness of CSPs in general, CSP solvers are pretty efficient if the constraints are sparse enough and not chosen adversarially.
Re:American Airlines Accidentally Let Too Many Pilots Take t... by Kliment on Thursday November 30, 2017 @01:12AM (#15813844)
a constraint solver, they're used heavily in CAD as well