CP-SAT for Manufacturing Scheduling: Finding a Plan That Follows Every Rule
A factory schedule has to follow thousands of rules at once, from the order of steps to deadlines. A program called CP-SAT searches for plans that do.
Why scheduling gets hard so fast
A real shop schedule is a long list of rules. Some jobs must wait for others to finish. Some can run on more than one machine. Machines have working hours, and no machine can run two jobs at once. Switching from one product to another takes setup time. Orders have deadlines, and some work is optional. Add a few more jobs and the number of possible plans explodes. That’s why an order of jobs that looks fine for one machine can be a poor plan for the whole shop.
CP-SAT is a solver: a program that searches for answers that follow all of your rules. It’s open-source (free for anyone to use) and part of Google’s OR-Tools. It mixes three ideas. Constraint programming lets you write the rules down directly and uses them to cross off bad options early. Boolean satisfiability (SAT) solving brings fast ways to juggle huge numbers of yes-or-no choices. Integer optimization finds the best plan when the answers have to be whole numbers. You also get to describe the problem in pieces that match the real shop. An interval variable stands for an activity, with a start, a length and an end. A Boolean variable is a true-or-false choice, like whether a job runs on machine A. And built-in rules called global constraints handle common scheduling logic directly, like never putting two jobs on one machine at once.
Be clear about the decision
A good model starts by sorting everything into three buckets. Decisions are what the solver gets to choose, like each job’s start time and which machine runs it. Hard constraints are rules that can never be broken. Think safety, steps that must come in order, and one job at a time per machine. The objective is the score the solver tries to make as good as possible. It might add up things you want less of, each weighted by how much you care. Those could be late orders, product switches (changeovers), piles of unfinished work (WIP) or a schedule that keeps changing.
The hard part usually isn’t running the solver. It’s deciding what must never be broken and what can be traded off. It’s also keeping the score in line with what really happens on the shop floor.
A small example app
A small Schedule Lab can let you change how much capacity there is and how tight the deadlines are. You can also change how many jobs have to wait on other jobs. Then it can show a schedule that follows every rule, along with its bottleneck (the slowest step, which holds everything else up). A version for a real factory could go further. It could start from the last good plan instead of from scratch (a warm start). It could plan a short window at a time and keep rolling it forward (a rolling horizon). It could lock the next part of the plan so it doesn’t change (a frozen zone). And it could explain why a move someone asks for would break the rules.