Print Shop Scheduling
Sequence-Dependent Setup Times
The Problem
In commercial printing, changing from one job to another requires setup operations: cleaning rollers, changing ink cartridges, swapping printing plates, adjusting paper guides, and recalibrating color registration. The time required for these changeovers depends on both the previous and next job. For example, switching from a dark-ink job to a light-ink job requires thorough roller cleaning to prevent color contamination, taking significantly longer than switching from light to dark. Similarly, jobs using the same paper stock require minimal plate adjustments, while switching paper types demands full recalibration.
This is modeled as a Permutation Flow Shop with Sequence-Dependent Setup Times (SDST). Each print job must pass through the same sequence of machines (printing press, then finishing/binding), and the setup time on each machine depends on the pair of consecutive jobs. The goal is to find the job ordering that minimizes the total completion time (makespan). This problem is NP-hard even for two machines.
Try It Yourself
Edit jobs, machines & setup times, then solve — 4 jobs, 2 machines
SDST Flow Shop Solver
The Algorithms
Constructive heuristic and metaheuristic approaches for SDST scheduling
NEH-SDST
Constructive HeuristicAn adaptation of the Nawaz-Enscore-Ham (1983) heuristic for sequence-dependent setup times. Jobs are sorted by total processing time plus average setup time in descending order, prioritizing jobs with the highest combined workload and changeover impact. Each job is then inserted at the position in the partial sequence that yields the minimum makespan, where the makespan calculation includes both processing and setup times.
1. For each job j, compute W(j) = sum(p[j][m]) + avg(setup[m][i][j]) for all m, i
2. Sort jobs by W(j) in descending order
3. Start with the first job in the sorted list
4. For each remaining job j in sorted order:
Try inserting j at every position in the current sequence
C[m][k] = max(C[m][k-1] + setup[m][prev][curr] + p[curr][m],
C[m-1][k] + setup[m][prev][curr] + p[curr][m])
Keep the insertion with minimum makespan
5. Return the final sequence
GRASP-SDST
A Greedy Randomized Adaptive Search Procedure adapted for the SDST flow shop. In each iteration, a solution is constructed using a randomized greedy procedure with a Restricted Candidate List (RCL) controlled by parameter alpha = 0.3. Candidates are evaluated by their total processing time plus setup time from the last scheduled job. After construction, a swap-based local search explores the neighborhood for improvements. The best solution across all iterations is returned.
1. Repeat for N iterations (default: 10):
a. Build initial sequence using randomized greedy:
- Compute cost(j) = sum(p[j][m]) + sum(setup[m][last][j]) for unscheduled j
- RCL = {j : cost(j) <= c_min + alpha * (c_max - c_min)}
- Select random job from RCL, append to sequence
b. Apply swap local search:
- For each pair (i, j), swap and evaluate makespan
- Accept if improved, repeat until no improvement
c. Update best solution if improved
2. Return best solution found
Real-World Complexity
Why industrial print scheduling is far harder than this example
Hundreds of Jobs
Commercial print shops handle 100-500+ daily jobs across catalogs, brochures, packaging, and labels. The solution space grows factorially with job count.
Color Sequencing
Ink changeover optimization: scheduling light-to-dark color progressions minimizes cleaning cycles and reduces waste from color contamination.
Multiple Presses
Different presses have different capabilities (sheet-fed vs. web, color count, max sheet size), creating an unrelated parallel machine environment.
Rush Orders
Priority jobs with tight deadlines arrive dynamically, requiring schedule disruption and re-optimization in real time.
Paper Changeovers
Switching paper type (weight, coating, size) requires mechanical adjustments and test runs, adding significant setup time between jobs.
Drying Constraints
UV vs. conventional inks have different drying times. Jobs may block the finishing machine until ink is fully cured, creating no-wait or blocking constraints.
Key References
Need to optimize your print production?
Discuss scheduling optimization for your manufacturing workflow