Why is Production Scheduling Hard?
Imagine that you plan a pie factory and you have 3 types of pie to make (apple, plum & cherry) but only 1 production line. When you change from one pie to another you have to clean the line, and the amount of cleaning depends on the sequence of products. For example, you might need 10 mins to switch from apple to plum, but 30 mins to switch from cherry to apple.
However, some pies might be needed more urgently than others so you need to decide on the best sequence that meets your customer orders while minimising wasted cleaning time.
For example, you could do apple first, then plum, then cherry. Or you could do cherry first, then apple, then plum. For this very simple case there are in fact 6 possible sequences, as shown to the right.
In theory we have to consider all 6 options and choose the best. In practice of course this would be very easy and take no time to work out.
However, imagine there are 4 types of pie instead. Now there are actually 24 different sequences, rather than just 6. As the number of types of pie increases the number of possible sequences grows VERY FAST as shown in the table below.
For 15 pies the number of possible sequences is huge: 1,307,674,368,000 (that's 1.3 trillion). For hundreds of pies there are more possible ways of scheduling the work than there are atoms in the universe!
To find the best solution (i.e. the one that meets customer requirements while minimising cleaning/changeover time and maximising efficiency) we should consider all possible sequences and pick the best. This is impossible so production planners use their intelligence, intuition and experience to do the best they can (bear in mind they have minutes or hours at most to find an answer, not years).
Of course this simple example does not take into account all the other complexities of a real factory (e.g. multiple lines, shelf-life, downtime, multi-stage process, employee availability), which makes the problem even harder to solve. However it illustrates how what seems to be a quite straightforward case quickly becomes very challenging. Most production planners will agree with this, but even they don't always realise just how complex their job really is.