There are more possible ways to arrange 59 distinct jobs in a line than the commonly estimated number of atoms in the observable universe. A modest production line can therefore generate a number of sequences that no computer could enumerate. At first glance, this seems to explain why scheduling can be so difficult.
But try a thought experiment. All 59 jobs are ready, they run on one continuously available machine, and there are no changeovers or deadlines. If our only goal is to finish the full workload as early as possible, every sequence takes exactly the same total processing time. A truly enormous set of alternatives has become a remarkably simple decision.
The size of the search space and the difficulty of the optimization problem are not the same thing.
A small change in the rules
Now suppose switching from one product to another requires cleaning the machine. Job order suddenly matters, because some sequences involve much more cleaning than others. Add a delivery deadline, and grouping similar products may no longer be the best choice. Add another machine that can run only certain products, and the decision becomes a combination of assignment and sequence. We have not necessarily created more jobs. We have changed how the decisions interact.
This is what makes combinatorial optimization interesting. Choices combine in ways that produce many possible outcomes, but some mathematical structures reveal efficient ways to navigate them and others resist convenient shortcuts. A complicated-looking problem can have an elegant solution. An innocent-looking problem can be difficult to solve or certify at scale.
The shortest-path algorithm does not solve the general traveling-salesperson problem, and finding a globally shortest tour can be computationally challenging.
The shortest path surprise
A road network can contain an extraordinary number of possible paths between two points. Yet for a graph whose edge costs are nonnegative, algorithms such as Dijkstra's can find shortest paths without listing every route. They use a mathematical property of shortest paths to rule out unnecessary work.
The traveling salesperson problem looks similar on a map: visit every required location and return to the starting point using the shortest tour. But this requirement couples the choices differently. The shortest-path algorithm does not solve the general traveling-salesperson problem, and finding a globally shortest tour can be computationally challenging. The landscape of possibilities matters more than the mere existence of many possibilities.
This explains why optimization researchers pay such close attention to problem structure: the mathematical relationships among decisions, constraints, and objectives. Those relationships determine which deductions, transformations, and search strategies are available.
Finding an answer versus knowing it is the best
There is another kind of difficulty that can be easy to miss. A solver may find an excellent feasible schedule quickly. Proving that no better feasible schedule exists can require much more computation.
But the most interesting question is not how many possible schedules exist.
Suppose we are minimizing cost. The solver has a schedule costing 102 units and a valid mathematical lower bound of 100. It knows the true optimum lies between 100 and 102, but it does not yet know exactly where. The schedule might be optimal, or a better one might exist. Whether another hour of computation is worthwhile depends on what the decision is for.
In live operations, an available, high-quality plan can be more useful than a certificate that arrives too late. In scientific research or some engineering applications, establishing optimality or a rigorous bound may be central to the task. Optimization technology should distinguish these goals, not collapse them into the vague promise of finding the best answer.
Where algorithms make the difference
Construction heuristics build a promising solution, often one decision at a time. Improvement heuristics start from a candidate and modify it, perhaps by swapping two jobs or rearranging a group of tasks. Exact algorithms can use mathematical bounds to eliminate whole groups of possible solutions without inspecting them individually. Many effective solvers combine several of these ideas.
The fascination is not that computers can check a lot of possibilities. It is that a carefully chosen algorithm can avoid checking most of them. Better understanding of the problem leads to better search, and better search changes what can be solved within the time available.
Fifty-nine jobs make a dramatic number. But the most interesting question is not how many possible schedules exist. It is what the problem allows us to learn about them without having to look at them all.
Continue learning
New to Optimization, part 3 of 6. Previous: Do I have an optimization problem?. Next: Variables, constraints and objectives. View the full learning path.