Job-Shop Scheduling (GA)

What is Job-Shop Scheduling and How Do Genetic Algorithms Solve It?

Job-shop scheduling assigns operations of multiple jobs to machines in a sequence that minimizes makespan (total completion time) or tardiness. Each job consists of an ordered sequence of operations, each requiring a specific machine for a specific duration. No two operations can share a machine simultaneously.

The job-shop scheduling problem (JSSP) is NP-hard. A Genetic Algorithm (GA) solves it by evolving a population of candidate schedules. Each chromosome encodes an operation sequence; POX (Precedence Operation Crossover) preserves job ordering while combining parents; swap mutation exchanges operation positions to explore new solutions.

JSSP is critical in manufacturing environments such as machine shops, semiconductor fabrication, and printing operations. A 10-15% reduction in makespan directly increases throughput without capital investment. Modern manufacturing execution systems (MES) use GA-based schedulers for real-time production planning.

Formula: Makespan = max(completion time of all operations) Tardiness = Σ max(0, Completion_j − DueDate_j) for each job j GA: Initialize population → Evaluate fitness → Select parents → POX Crossover → Swap Mutation → Replace → Repeat

Example Calculation

3 jobs, 3 machines. Job 1: M1(3)→M2(2)→M3(4). Job 2: M2(4)→M1(3)→M3(2). Job 3: M3(2)→M2(3)→M1(1). Optimal makespan = 12 time units. A GA with population=100, generations=200 typically finds this optimum or a solution within 5% (makespan 12-13).

When to Use This Calculator

• A production planner scheduling multiple jobs across a machine shop with shared equipment to minimize completion time
• A manufacturing engineer evaluating the impact of adding a new machine or changing operation sequences on overall throughput
• A scheduler at a print shop or semiconductor fab determining job priorities to meet customer due dates with minimal tardiness
• An operations researcher benchmarking GA-based scheduling against current manual or priority-rule scheduling methods

Common Mistakes to Avoid

• Setting population size too small for complex problems — with 10+ jobs and 5+ machines, use at least 100-200 individuals to maintain genetic diversity and avoid premature convergence
• Running too few generations and accepting a suboptimal solution — monitor whether the fitness is still improving; if it plateaus, the solution has converged; if still improving, increase generations
• Ignoring release times and due dates when they exist — without these constraints, the GA optimizes makespan only, which may produce schedules that violate real-world timing requirements
• Not running the GA multiple times with different random seeds — GA is stochastic; a single run may get trapped in a local optimum; run 3-5 times and take the best result

How to Interpret Results

• If total tardiness is zero, all jobs complete before their due dates — the schedule is feasible and the focus should shift to reducing makespan further
• If makespan is close to the sum of processing times on the bottleneck machine, the schedule is near-optimal — little room for improvement remains
• The Gantt chart reveals idle time on machines: large gaps indicate scheduling inefficiency or unavoidable sequencing constraints

Related Standards & References

• Garey, Johnson & Sethi (1976) — established the NP-hardness of job-shop makespan minimization
• Makespan (C_max) and total tardiness — the standard objective functions in production scheduling
• Genetic algorithms (Holland, 1975) — the metaheuristic class applied here to search the schedule space

Frequently Asked Questions

How do I set GA parameters for good results?

Start with population size = 50-200, mutation rate = 0.05-0.15, and 200-500 generations. Larger populations explore more solutions but run slower. Higher mutation rates prevent premature convergence but slow convergence speed. For problems with 10+ jobs, use population ≥ 100 and generations ≥ 300.

What is the difference between makespan and tardiness optimization?

Makespan minimization focuses on finishing all jobs as quickly as possible — ideal for maximizing throughput. Tardiness minimization prioritizes meeting due dates — critical for customer commitments. These objectives can conflict: the shortest makespan may cause some jobs to be late. Multi-objective optimization can balance both.