Online print shop scheduling
Online orders arrive in large numbers, and most of them are small. Their requirements vary, and that variety makes production planning harder. Each order goes through a series of steps, and the steps are not the same for every order. A step can run on more than one machine, and those machines are not equally fast. A planner must choose a machine for every step and set the time each step starts. The same problem appears outside printing, in sheet metal fabrication and in aircraft overhaul. This page uses a commercial print shop as its example. The walkthrough sets out the constraint model, solves one small instance with OpenConstraint, and has the answer checked.
The problem
An online print shop sells through a web storefront and produces every order on one shared set of machines. The word "online" describes the sales channel. It does not mean online scheduling, where decisions must be made before future work is known. All work for a planning run is known before that run starts.
Each scheduling job is a set of operations. It may represent one customer order or several orders combined beforehand. It may consist of a single operation, or several operations linked by prerequisites. Those prerequisites only connect operations in the same job; operations in different jobs have no precedence relation. Printing a batch of flyers is one operation, and trimming it afterward is another. These links do not have to form a single chain. They can branch, allowing different parts of the same job to run at the same time on different machines. For example, a book job can print its cover and its pages separately, then bring them together in a binding operation.
Each operation has a completion fraction that applies to every direct successor. A later operation may start once that fraction of its predecessor has been processed. That point can come before the predecessor is fully complete. Cutting can begin once half of a printing run is finished, for example. But a successor cannot finish before its predecessor does.
For every operation, a planner must decide which eligible machine will process it and when it will start. Together, these choices determine the order of work on each machine. A machine handles only one operation or setup at a time. Processing times differ by machine. Setup is needed before processing. The first operation on a machine has its own setup time. Later setup times can depend on the preceding operation. Switching between paper types or ink colors can require extra cleaning or adjustment. A setup cannot be interrupted and ends exactly when processing begins.
Every operation also has a release time and cannot start before it. Some operations may be fixed in advance to a specific machine and start time. These represent work still running from an earlier plan, as well as work that must happen at an agreed time — such as when a customer visits to watch their order being produced.
Machines may not be available all the time. Planned maintenance and shift patterns can make a machine unavailable for a known period, such as an overnight closure. If processing reaches such a period, it pauses, stays on that machine, and resumes as soon as the machine is available again. It cannot be moved to another machine or displaced by other work. For example, a long print run may reach the end of the day’s production shift, pause for the night, then resume on the same press the next morning.
A plan is judged by when its last operation finishes. The goal is to make that finish time as early as possible. A shorter production schedule can reduce labor and electricity costs.
The model boundary
Before scheduling, a separate step can combine printing operations from several customer orders onto one sheet. Printers call this ganging, and it is a cutting-stock decision rather than a scheduling one. The orders joined that way form a single scheduling job, and a later cutting operation can split that job into branches that run in parallel when machine capacity allows. This model takes that job structure as input. It does not decide which orders to combine.
The set of work is fixed before planning starts. This model has no due dates, priorities, or delivery commitments. It does not handle new orders that arrive during a run, and it does not plan again once a run has begun.
Where the data comes from
The worked example below is authored for this page. Its machines, times, and jobs were chosen to show the model working, and no real print shop supplied them. This section answers a different question. If a print shop wanted this model run on its own work, where would the numbers come from?
A print shop already holds almost all of them. The model needs no new measurement program and no new system. It needs the numbers production records day to day, exported once per planning run.
Systems that already hold it
- Management information system. Open orders, their quantities, and their routes through the shop provide the jobs and operations.
- Equipment records. The presses, cutters, and binders that can run each operation identify the eligible machines; their recorded speeds give processing times.
- Setup or changeover matrix. Production engineering records the time lost switching a machine between kinds of work, providing sequence-dependent setup times.
- Maintenance and shift calendars. Periods when a machine is unavailable provide the unavailability windows.
A small worked example
This instance has four machines and three jobs. The machines are a digital press, an offset press, a cutter, and a binder.
The flyers job has two operations: print-flyers, then trim-flyers. Trim-flyers may start once 60 percent of print-flyers has been processed, but cannot finish before print-flyers finishes.
60%
The poster job has one operation, print-poster. It cannot start before tick 2 and is fixed to the offset press at tick 4, where it runs until tick 7.
The book job has three operations: print-pages and print-cover run independently of each other, and bind-book needs both of them finished before it can start.
The digital press is unavailable from tick 5 to tick 7 for planned maintenance. Any operation already running on that press pauses at tick 5 and resumes at tick 7.
The table below gives the processing and setup times for each eligible operation–machine pair, in ticks. “First setup” applies when no operation precedes it on that machine. In “Later setup,” “Any” means the setup time is the same for every possible predecessor.
| Machine | Operation | Processing | First setup | Later setup |
|---|---|---|---|---|
| digital-press | print-flyers | 10 | 2 | print-pages: 2; otherwise: 3 |
| digital-press | print-poster | 8 | 2 | Any: 3 |
| digital-press | print-pages | 7 | 3 | print-cover: 1; otherwise: 3 |
| digital-press | print-cover | 7 | 3 | print-pages: 1; otherwise: 3 |
| offset-press | print-flyers | 6 | 5 | Any: 9 |
| offset-press | print-poster | 3 | 4 | Any: 9 |
| offset-press | print-pages | 5 | 5 | print-cover: 2; otherwise: 9 |
| offset-press | print-cover | 5 | 5 | print-pages: 2; otherwise: 9 |
| cutter | trim-flyers | 4 | 2 | Any: 3 |
| cutter | bind-book | 5 | 3 | Any: 3 |
| binder | trim-flyers | 6 | 3 | Any: 3 |
| binder | bind-book | 3 | 2 | Any: 3 |
Optimal schedule
The OpenConstraint MCP server ran the CP-SAT model. CP-SAT proved this schedule optimal, and the checker accepted it. This result comes from a small instance authored for this page. It is not a customer schedule, benchmark result, or production run.
- Running the machine is processing an operation
- Setup the machine is being changed over
- Unavailable planned maintenance or a shift closure
- Idle the machine has nothing to run
- Must finish first a precedence link between operations
The optimal schedule runs print-pages then print-cover on the digital press, with a 1-tick changeover. On the offset press, fixed print-poster is followed by print-flyers, which incurs a 9-tick changeover. Trim-flyers starts once 60 percent of print-flyers is processed and finishes last at tick 24.
A non-optimal fixed-order schedule
For comparison, a fixed rule takes the operations in the order listed in the instance. For each operation, it picks the eligible machine that can finish it first after accounting for processing time, setup, maintenance, and already scheduled work. With print-flyers listed first, the schedule ends at tick 27. If print-pages and print-cover came first, the same rule would reach 24 ticks.
- Running the machine is processing an operation
- Setup the machine is being changed over
- Unavailable planned maintenance or a shift closure
- Idle the machine has nothing to run
- Must finish first a precedence link between operations
The CP model
The completed schedule assigns each operation to a machine and gives it a start time. The constraint programming (CP) model turns the print shop’s scheduling rules into variables, constraints, and an objective. The excerpts below show selected parts of the model in Python.
Assigning operations to machines
For each operation, the model creates a true-or-false variable for every machine that can run it. When the variable is true, the operation runs on that machine.
operation_assignments: list[CpsatIntVar] = []
for machine_index, (machine_id, machine_option) in enumerate(
operation.machine_options.items()
):
is_assigned: CpsatIntVar = model.new_bool_var(
f"is_assigned_{operation_suffix}_{machine_index}"
)
assignments[operation_id, machine_id] = is_assigned
# …
operation_assignments.append(is_assigned)Exactly one of these variables must be true for each operation. This assigns every operation to one eligible machine.
model.add_exactly_one(operation_assignments)Sequencing work and setup
For each machine, the model adds a circuit constraint that links the assigned operations through a virtual start-and-end node, called the depot in the model. The last operation links back to this node to close the circuit for the solver; the production order itself still runs from first to last. For each possible link between two operations, is_machine_transition is true when the solver selects it. A selected link sets the successor’s transition setup time. The setup ends when the successor starts and cannot begin before the predecessor finishes.
for candidate_machine_predecessor_operation_id in eligible_operation_ids:
for candidate_machine_successor_operation_id in eligible_operation_ids:
# … skip identical pairs and create is_machine_transition
sequence_arcs.append(
(
node_index[candidate_machine_predecessor_operation_id],
node_index[candidate_machine_successor_operation_id],
is_machine_transition,
)
)
# … record the predecessor and look up the matching setup time
model.add(
setup_durations[candidate_machine_successor_operation_id]
== machine_transition_setup_duration
).only_enforce_if(is_machine_transition)
model.add(
setup_starts[candidate_machine_successor_operation_id]
+ machine_transition_setup_duration
== processing_starts[candidate_machine_successor_operation_id]
).only_enforce_if(is_machine_transition)
model.add(
processing_ends[candidate_machine_predecessor_operation_id]
<= setup_starts[candidate_machine_successor_operation_id]
).only_enforce_if(is_machine_transition)
model.add_circuit(sequence_arcs)Keeping fixed work and job order
A fixed operation keeps its assigned machine and start time. The model schedules everything else around it.
if operation.fixed is not None:
# A fixed operation still participates in its machine's sequence.
model.add(assignments[operation_id, operation.fixed.machine] == 1)
model.add(processing_start == operation.fixed.start)A successor may start after the required fraction of its predecessor has been processed. It still cannot finish before its predecessor.
for successor_operation_id in operation.successors:
model.add(
processing_starts[successor_operation_id] >= theta_completion_times[operation_id]
)
model.add(processing_ends[successor_operation_id] >= processing_ends[operation_id])Minimizing the last finish time
The makespan is when the last operation finishes. The model makes that time as early as possible.
makespan: CpsatIntVar = model.new_int_var(0, horizon, "makespan")
model.add_max_equality(makespan, list(processing_ends.values()))
model.minimize(makespan)How the result is checked
For the returned schedule, an independent checker verifies assignments, timing, setup, maintenance windows, precedence, and makespan against the input data. Its checks cover the encoded rules, not whether those rules match the production floor.
An accepted check confirms feasibility; the solver’s “optimal” status proves that no feasible schedule finishes sooner for this model and input data.