Optimisation Techniques and Their Application to Production Scheduling

This paper is a short resume of various optimization techniques and their application to production scheduling. Descriptions of four different optimization techniques are given. The use of each technique is described in the context of real-world production scheduling decision-making environments.

Linear Programming

The 'Standard Form' of Linear Programming is to minimize an objective function e.g. 'minimize x' where x is a set of variables, and there are some constraints in the form Ax = b where A and b are coefficients.

A typical example of how Linear Programming could be used in a production scheduling environment would be a chemical or other process industry company. The objective function would be to minimize the number and determine the size of the production batches required. This would take into account the sales orders, minimum and maximum production batches, tank sizes, and other constraints.

Integer programming is a more realistic version of linear programming for production scheduling applications where in some cases resources are either available or not available but nothing in between.

The main benefit of linear programming is that it determines the optimum batch sizes to make, but for most manufacturing companies their production batch sizes are determined by their ERP system, so all they require is sequencing of the ERP orders. Under these circumstances linear programming is of little use.

Complete Enumeration and Branch and Bound

Complete enumeration can be best described as saving a schedule after changing every possible value of every variable that you want to test your objective function against. You then select the schedule that best meets your objective. For example if your objective function is to minimise cost, and you decide you are going to use alternative routes as the variable, then you generate and save a schedule for each possible alternative route (and alternative resources for each operation).

The literature describes various bounding techniques that aim to limit the size of the enumeration. These tell you as you change a variable whether the result of your objective function is increasing or decreasing (such as a moving average) and so whether to continue saving more results as you change that variable or leave that one and go onto the next variable.

The problem is that for the bounding techniques to work effectively the variables must be completely independent, and in production scheduling they rarely are. If you have, say, a constraint on the number of tools available and the number of operators, the two constraints will interact. If you increase the tools there will be no benefit because you run out of operators, and vice-versa. This means that you have to go back to a complete enumeration to find the solution.

With the number of variables required to describe a typical production schedule complete enumeration is, to say the least, a processor intensive activity, and it is simply not practical with today's technology to use this technique.

Genetic Algorithms

Genetic Algorithms work in an iterative manner similar to Branch and Bound, except that you test each variable in turn and save the best overall result for that variable (i.e. the winner in that generation). This is repeated for each variable and the result is a set of schedules. Each one represents the best result for one of the variables.

In a production scheduling environment, a, say, minimum cost schedule may have been achieved with three operators (keeping all the other variables such as tools, setters, shift patterns etc. constant and, in the case of the secondary resources, un-constrained). Another minimum cost schedule may have been achieved with two setters, once again keeping the other resources un-constrained whilst testing the number of setters required.

You then combine these variable settings together to form their best generation winners, and then go through the same tests in another generation (obviously a smaller population this time) and repeat until you only have one winner.

As with Branch and Bound, you only change one variable at a time and if the variables interact you may well miss the best result. This points you back to a complete enumeration and the problems highlighted in the other methods.

Heuristics

Heuristics in the literature generally refers to 'rules of thumb' or 'best practise' for the selection of the 'best' job to do next on a particular resource, e.g.. LPT (longest processing time first) or SPT (shortest) etc. are heuristic rules.

In a production scheduling environment heuristic rules are used to do step-wise local optimization using these 'rules of thumb', e.g. if you've just made a red Widget then make another red one to minimise the changeover time, or if none are available make an orange one.

A heuristic solution is a good, feasible schedule, but it is not guaranteed to be optimal.

Conclusion

Linear and integer programming have long been accepted as successful scheduling techniques in process industries, but their application to other manufacturing is limited because of clashes with ERP functionality, and the complexity of setting up the required equations.

Branch and Bound and Genetic Algorithms can potentially solve manufacturing problems, but as yet the complete enumeration required means that it would take many days to create a schedule.

Heuristics are well-known and accepted in most production scheduling environments and have been developed over many years for particular applications (for example we always put product 'x' before product 'y' on resource 'A'). Most production scheduling systems use heuristics to locally optimise the schedule at each decision point. Such schedules are good and feasible, but are unlikely to be truly optimal.