Scheduling Problems 101
by Adam Kehoe
The Opex 101 series is an introduction to the tools, trends, and techniques that will help you make the most of your organization’s data. Intended for business leaders and practitioners alike, these posts can help guide your analytics journey by demystifying essential topics in data science and operations research.
If you’ve ever wondered whether there was a way to decide what gets done, where and when it should happen, and what or whom should do it, then this introduction to scheduling theory just might be for you.
(Or not, but hopefully so.)
The concept is not so foreign — all great things have required scheduling as part of their creation, including the Pyramids, the Parthenon, and the wondrous sensory delights of pizza. Though scheduling theory as a distinct academic field didn’t arise until the 1950s, as a subset of operations research (OR) it was created to provide analytical frameworks with which to optimize decision-making.
Traditionally, scheduling problems comprise machines — anything that does work — and jobs — the work to be done. In a scheduling theory context, machines can be thought of as people, or airports, or literal machines (like in a factory). Jobs can be thought of as jobs — not much creativity needed there.
In the simplest such problems, each machine is assigned a processing rate, which determines how quickly it can complete a job, and the goal is to order a set of jobs into an optimal schedule. However, there are often constraints that bring complexity to the problem. Some classic examples include a necessary job sequence (e.g. gold needs to be mined before it’s refined, and refined before it’s turned into necklaces), or a hard deadline for job completion (e.g. a pizza needs to be delivered while it’s still hot, or by a pizzeria-guaranteed time). The decisions to be made, then, chiefly concern two tasks: (a) assigning jobs to machines, and (b) specifying the order in which these jobs are to be completed.
The reason for the emergence of this field of study (like much of operations research, it seems) is that even the simplest of scheduling problems admits a large number of possible solutions. A scheduling task that involves a single machine processing 10 jobs contains 10! (or about 3.6 million) possible job orders. Even in these very simple cases, enumeration often fails, meaning that alternative methods need to be employed in any practical situation. (You can read more about the challenges of enumeration in operations research in our Opex 101 post on vehicle routing problems.)
Like any other OR problem, a scheduling problem’s formulation involves setting an objective. This can differ based on the business or organization’s priorities. The objective is typically cost minimization, but the “cost” in a scheduling context is usually some time-related measure. (However, the specific metric to be minimized could vary.)
For example, if you’re an employee designing your factory’s schedule, you might want the completion time of your factory’s last job to be as soon as possible, allowing you to go home early that day. Perhaps you want to minimize the sum of your jobs’ completion times; this would make most sense if there’s a time discount factor present, such that the benefit for completing a job declines over time. Maybe some jobs need to be completed by a certain time, and if those deadlines aren’t met, a tardiness penalty is incurred.
In short, depending on what your objective is, one scheduling method or heuristic might be more suitable than others.
In order to illustrate, let’s take a problem wherein the goal is to minimize the total weighted completion time of a set of jobs. Consider a factory that uses a single machine. Let’s say (a) that this machine can produce ten types of products, and (b) that each product has an associated completion time (i.e. a cost), as well as an associated weight (e.g. a price). The faster the factory can produce these products, the faster its parent company can sell them.
One option is to formulate this as a mixed-integer program:
Here, the first constraint defines the completion time as the sum of the processing times for all jobs scheduled before it with its own processing time, and the next two constraints state that (a) only one job can be scheduled per position, and (b) each position can have only one job scheduled at a time.
You could give this formulation to an MIP solver and get a solution. However, this problem can be solved more quickly using a rule known as “Weighted Shortest Processing Time (WSPT)” instead. This heuristic suggests that jobs be scheduled in order of their completion-time-to-weight ratio, such that jobs with greater rewards and shorter processing times are scheduled first (maximizing your bang for your buck).
Many classical OR problems can be formulated as scheduling problems, which often leads to better solutions through the use of scheduling heuristics, or an alternative interpretation that aids understanding. For instance, the classic traveling salesman problem can be thought of as a scheduling problem by considering the cities as machines and the distances between them as set-up times, with the salesman as the job that needs to be processed by each machine.
Scheduling theory is a relatively new field with many applications across operations research. Whether for reformulation, insight, or direct application, scheduling theory is certainly a useful tool for a practicing operations researcher.
If there’s a topic you’d like us to cover as part of Opex 101, let us know in the comments below!
_________________________________________________________________
If you liked this blog post, check out more of our work, follow us on social media (Twitter, LinkedIn, and Facebook), or join us for our free monthly Academy webinars.
