4 ms·

One thing to note is that airline crew scheduling is np-hard (trivially you can reduce Hamiltonian cycle to it). Ak interesting semi-empiricle fact about np-com

One thing to note is that airline crew scheduling is np-hard (trivially you can reduce Hamiltonian cycle to it). Ak interesting semi-empiricle fact about np-complete problems. Take a decision problem to determine if there is a schedule with k crews. Now there is some k’ that is the minimum such k. For many Np problem problems the difficulty of the decision problem is related to the ratio of k to k’. (Not all decision problems are like this… those that are are on the complexity class APX. As a quick rule of thumb however this works) In terms of airline scheduling this means that if you more crews than you strictly need, your algorithm is probably going to successfully schedule them. When the number of crews drops below some critical value… all hell breaks loose. Thinking about this in complexity terms is useful I think. He issue isn’t just bad software… with a small enough number of crews, all software is bad, unless P = NP

maxerickson 4y ago
I wonder if the difficulty at this point is algorithmic, or if they even have the data to make "reasonable" decisions, never mind optimizing them. Like what do they do with the bags that are sitting on the plane for cancelled flights? Store them where they are? Figure out their origin and start queuing them to be sent there? Try to get information from the passenger about where to send it? And then with planes and crews, do they even have "potential" flights where they would be able to reliably seat a worthwhile number of passengers?
- chasd00 4y ago
  yeah it sounds like recovering from this requires standing up a brand new organization in real time. I hope someone is watching the trouble ticket system, imagine that going down...
  - deleted 4y ago
    [deleted]
- bodhiandphysics 4y ago
  I'm sure they know exactly where every plane and every flight crew is at every moment. My point about algorithmic complexity is that even with perfect knowledge, fixing this is a computationally difficult problem. The idea was to show how the properties of algorithms that perform combinatorial optimization actually matter!
  - anon84873628 4y ago
    The statements from employees indicate that SWA does _not_ know where flight crews are at every moment. When a flight is cancelled the downstream information is not updated accordingly. Crew have to call a phone line and speak to another human to update their information and assignments. With the large scale cancellations due to weather, that system was overloaded and fully collapsed. SWA had no choice but to cancel the majority of their flights while they sort out where the crews are at and how to schedule them next. The debacle is a direct result of lack of investment in modern software systems.
    - chasd00 4y ago
      heh i wonder if they've asked everyone to use their phones to share their location with their immediate supervisor. Then someone setup a spreadsheet in sharepoint and the supervisors are going at it.
  - enneff 4y ago
    > I'm sure they know exactly where every plane and every flight crew is at every moment. The story being circulated by Sw employees is that this is the failure. The system needs to be manually updated when flights are cancelled or changed, and in this situation with a cascading failure they have completely failed to keep that data accurate. SW employees have said they have spent 24 hours on hold trying to inform the company where they are. I don’t think this has anything to do with algorithmic complexity.
- SoftTalker 4y ago
  > Like what do they do with the bags that are sitting on the plane for cancelled flights? Eventually you send them back to the passenger's home address. I've had lost luggage before that turned up on my front porch a week later, some courier service had dropped it off.
someguydave 4y ago
Maybe there are many crews who are not able to fly because they hit the FAA hour limit? If so, then this cascade of failure was predictable.
- noirbot 4y ago
  Predictable, assuming they knew which crews in which cities were close to their limit, which it seems like they don't now that the system is down, which is most of the problem.
raverbashing 4y ago
Yes, theoretically it is NP, if you approach it naively. In practice it is easier to optimize for sub-problems In practice, crews have their home base, their corresponding qualifications (though for WN they probably only have one or two types) And you can bet you can start cancelling flights once you don't have enough crew. Problem is, your crew might have gone over their allowed time and them (and your plane) are in Smallville, OH and there are passengers in Chicago waiting to fly.
- tgv 4y ago
  Also: you can work with sub-optimal solutions. Decent approximations exist for many classes of certain problems. Even running simulated annealing or genetic algorithm will get you close to the optimum. I'm sure such a large airliner has a staff with sufficient knowledge of optimization.
  - bodhiandphysics 4y ago
    I do simulated annealing for a living. Simulated annealing on graphs works great when a) the diameter of the graph is small (which for airlines corresponds to hubbie hub and spoke models) and b). when you can accept relatively approximate solutions. The issue it seems here is that southwest doesn't have enough pilots. Algorithmically, that means they can't accept approximate solutions!
    - raverbashing 4y ago
      > Algorithmically, that means they can't accept approximate solutions! Well, of course they can Not enough pilots make the general problem infeasible, so you have to make do what you have In practice this means a) flying the schedule as best as you can b) get people/crew/planes back to hubs c) prioritize based on displaced people/cost/other variables
      - bodhiandphysics 4y ago
        You have to be careful what you mean by approximate. In this context, it means a schedule that requires more than the optimal number of pilots. Another way of meaning approximate is canceling routes till you can find a schedule that fits the pilots you have. That’s actually a harder problem, and is not CS means by an approximation algorithm. Obviously that’s what SW has to do, but part of the reason why things are so disastrous is that this problem is quite difficult (in terms of algorithmic difficulty)
rossdavidh 4y ago
While this would be an excellent justification for not being able to schedule everything, it's not much of a justification for not being able to schedule 2/3 of your flights on a day with clear weather...
hagmonk 4y ago
I don't get to exercise my dusty algorithms knowledge nearly enough to follow this nearly as well as I'd like. Are we talking about the bin packing problem and approximation ratios? So, is the intuition here that when the ratio of bins to objects goes up, the worst-case performance for the algorithm goes down into the toilet?

maxerickson 4y ago

I wonder if the difficulty at this point is algorithmic, or if they even have the data to make "reasonable" decisions, never mind optimizing them. Like what do they do with the bags that are sitting on the plane for cancelled flights? Store them where they are? Figure out their origin and start queuing them to be sent there? Try to get information from the passenger about where to send it? And then with planes and crews, do they even have "potential" flights where they would be able to reliably seat a worthwhile number of passengers?

chasd00 4y ago
yeah it sounds like recovering from this requires standing up a brand new organization in real time. I hope someone is watching the trouble ticket system, imagine that going down...
- deleted 4y ago
  [deleted]
bodhiandphysics 4y ago
I'm sure they know exactly where every plane and every flight crew is at every moment. My point about algorithmic complexity is that even with perfect knowledge, fixing this is a computationally difficult problem. The idea was to show how the properties of algorithms that perform combinatorial optimization actually matter!
- anon84873628 4y ago
  The statements from employees indicate that SWA does _not_ know where flight crews are at every moment. When a flight is cancelled the downstream information is not updated accordingly. Crew have to call a phone line and speak to another human to update their information and assignments. With the large scale cancellations due to weather, that system was overloaded and fully collapsed. SWA had no choice but to cancel the majority of their flights while they sort out where the crews are at and how to schedule them next. The debacle is a direct result of lack of investment in modern software systems.
  - chasd00 4y ago
    heh i wonder if they've asked everyone to use their phones to share their location with their immediate supervisor. Then someone setup a spreadsheet in sharepoint and the supervisors are going at it.
- enneff 4y ago
  > I'm sure they know exactly where every plane and every flight crew is at every moment. The story being circulated by Sw employees is that this is the failure. The system needs to be manually updated when flights are cancelled or changed, and in this situation with a cascading failure they have completely failed to keep that data accurate. SW employees have said they have spent 24 hours on hold trying to inform the company where they are. I don’t think this has anything to do with algorithmic complexity.
SoftTalker 4y ago
> Like what do they do with the bags that are sitting on the plane for cancelled flights? Eventually you send them back to the passenger's home address. I've had lost luggage before that turned up on my front porch a week later, some courier service had dropped it off.

someguydave 4y ago

Maybe there are many crews who are not able to fly because they hit the FAA hour limit? If so, then this cascade of failure was predictable.

noirbot 4y ago
Predictable, assuming they knew which crews in which cities were close to their limit, which it seems like they don't now that the system is down, which is most of the problem.

raverbashing 4y ago

Yes, theoretically it is NP, if you approach it naively. In practice it is easier to optimize for sub-problems In practice, crews have their home base, their corresponding qualifications (though for WN they probably only have one or two types) And you can bet you can start cancelling flights once you don't have enough crew. Problem is, your crew might have gone over their allowed time and them (and your plane) are in Smallville, OH and there are passengers in Chicago waiting to fly.

tgv 4y ago
Also: you can work with sub-optimal solutions. Decent approximations exist for many classes of certain problems. Even running simulated annealing or genetic algorithm will get you close to the optimum. I'm sure such a large airliner has a staff with sufficient knowledge of optimization.
- bodhiandphysics 4y ago
  I do simulated annealing for a living. Simulated annealing on graphs works great when a) the diameter of the graph is small (which for airlines corresponds to hubbie hub and spoke models) and b). when you can accept relatively approximate solutions. The issue it seems here is that southwest doesn't have enough pilots. Algorithmically, that means they can't accept approximate solutions!
  - raverbashing 4y ago
    > Algorithmically, that means they can't accept approximate solutions! Well, of course they can Not enough pilots make the general problem infeasible, so you have to make do what you have In practice this means a) flying the schedule as best as you can b) get people/crew/planes back to hubs c) prioritize based on displaced people/cost/other variables
    - bodhiandphysics 4y ago
      You have to be careful what you mean by approximate. In this context, it means a schedule that requires more than the optimal number of pilots. Another way of meaning approximate is canceling routes till you can find a schedule that fits the pilots you have. That’s actually a harder problem, and is not CS means by an approximation algorithm. Obviously that’s what SW has to do, but part of the reason why things are so disastrous is that this problem is quite difficult (in terms of algorithmic difficulty)

rossdavidh 4y ago

While this would be an excellent justification for not being able to schedule everything, it's not much of a justification for not being able to schedule 2/3 of your flights on a day with clear weather...

hagmonk 4y ago

I don't get to exercise my dusty algorithms knowledge nearly enough to follow this nearly as well as I'd like. Are we talking about the bin packing problem and approximation ratios? So, is the intuition here that when the ratio of bins to objects goes up, the worst-case performance for the algorithm goes down into the toilet?