Operations research: the tool you didn’t know you needed

Operations research deals with a class of problems that is ubiquitous in the industry, such as scheduling and supply chain management. However, these problems are not easily solved (or even solvable, for that matter) by everyday mathematics or trending technologies, for example machine learning and data mining. Let’s dive straight into a simplified example of a scheduling and path-finding problem that is often encountered in industry.

Figure 1: Mining quarry with four operation sites and roads.

Suppose there is a mining quarry consisting of four key locations positioned on the four corners of a rectangle (Figure 1). Quarry trucks traverse between these locations on single lane roads on a fixed schedule to maximise operational efficiency. Ongoing works at extraction sites make the dirt floor uneven thereby mandating periodic maintenance by a grader. The goal of the problem is to schedule a path for the grader to visit all sites without interrupting the quarry trucks.

Using operations research to tackle a problem like this generally consists of four key steps (in Figure 2):

1. Define variables that can describe any given state of the problem. For the current example, a multidimensional array can be used to track the grader’s departure time from any location as it heads to another destination. The scheduling problem is considered finished when correct values have been found for all entries in the multidimensional array.
2. Write constraint equations for the variables that match the constraints of the problem statement. For example, the entries in the array must ensure that the path taken by the grader at any time is never occupied by the quarry trucks. It’s also important to mention here that common sense constraints also need to be considered explicitly. For example, the grader cannot simultaneously leave two locations at the same time, and it cannot arrive at one location but immediately leave from another. 
3. Determine a cost function that is minimised/maximised. An obvious choice is to minimise the final departure time of the grader so that the job is finished as soon as possible. As an alternative problem, the cost function (and associated constraints) can be set to maximise the number of sites visited in a fixed amount of time.
4. Find the solution using exact, heuristic, or approximation methods. While exact methods (e.g. linear programming) can be used to find an optimal solution, they are often infeasible for large problems due to the NP nature of the problem. Heuristic methods lead to a relatively ‘good’ solution within a prescribed timeframe, but it is possible that the ‘good’ solution found is still far from optimal. Approximation methods guarantee the found solution is within a fixed percentage of the optimal using a polynomial-time algorithm, which means the computational time may (though not necessarily) be longer as compared to heuristic methods, but not necessarily prohibitive like for exact methods.

Figure 2: Four steps in operations research.

We hope this blog sheds light on how operations research can solve some business problems that often feel solvable but are somehow always slightly out of reach. Feel free to reach out to us and we will be more than happy to discuss your business-specific questions.