Production Scheduling
Assign jobs to machines in optimal sequence, minimizing idle time and makespan while respecting setup times, shift patterns, and priority orders.
NP-hardComplexity
Why Production Scheduling Is Hard
Sequence-dependent setup times
The time to switch from product A to B differs from B to A. This asymmetry makes the sequencing problem much harder than simple assignment.
Multi-machine dependencies
A job may need Machine 3 first, then Machine 7, then Machine 3 again. Blocking and deadlocks are possible. The interactions span the full shop floor.
Multiple conflicting objectives
Minimize makespan, maximize throughput, minimize changeovers, meet due dates. These objectives compete. Improving one usually worsens another.
Real-World Example
What This Looks Like in Practice
A factory runs 28 machines across 3 shifts. This week, 340 jobs need scheduling. Machine 7 requires a 90-minute changeover when switching product families. Machine 12 is down for maintenance Tuesday afternoon. A VIP order arrived 2 hours ago and must ship by Friday. A planner has been rearranging the schedule for 4 hours. The result is feasible but leaves 22% of machine time idle. kint finds a schedule with 22% less idle time in under 5 minutes. With a proven optimality gap.
Approach
How kint Solves Production Scheduling Problems
Model as Constraint Program
Jobs, machines, time slots, setup matrices, shift patterns. Each becomes a variable or constraint in a formal model.
CP-SAT explores the space
Google's CP-SAT solver uses constraint propagation to prune impossible assignments, then searches systematically for the best sequence.
Hybrid for large instances
For very large problems, kint combines CP with MIP relaxation to find tight bounds and near-optimal schedules faster.
Gantt chart with gap reporting
The result is a visual schedule with a proven quality metric. You see exactly how close to optimal the schedule is.
Technical Details
Job shop and flow shop scheduling problems are among the hardest combinatorial optimization problems. kint models these as constraint programs or mixed-integer programs depending on problem structure, using CP-SAT for discrete scheduling and MIP for continuous time models.
Impact
What Changes
Machine idle time
18-25%
Reduced by 22%
Changeovers
45/week
28/week (-38%)
Makespan
Baseline
-15%
Rush order response
3 hours replanning
5 minutes
Schedule creation
4-6 hours
Under 5 minutes
Example
Input
Schedule 340 jobs across 28 machines with setup time constraints, 3-shift patterns, and due date priorities.
Output
Optimal job sequence with 22% less idle time and 15% higher throughput. All due dates met.
-22%
idle time
+15%
throughput
5 min
solve time
Have a Production Scheduling Problem?
Show us your data. We'll show you what optimal looks like. No commitment.