[Paper] Cost Optimization in Production Line Using Genetic Algorithm

Source: arXiv - 2601.00689v1

Overview

This paper tackles a classic production‑line challenge: assigning a set of inter‑dependent tasks to workstations so that the overall manufacturing cost is as low as possible. By framing the problem as a combinatorial optimization task and solving it with a Genetic Algorithm (GA), the author demonstrates a practical, code‑friendly alternative to heavyweight analytical methods.

Key Contributions

• Two GA chromosome designs – a station‑based encoding (genes represent whole stations) and a task‑based encoding (genes directly map each task to a station).
• Adapted GA operators (crossover, mutation, selection, replacement) that guarantee feasibility with respect to precedence and station‑duration limits.
• Empirical comparison across three precedence patterns (tightly coupled, loosely coupled, uncoupled) showing the task‑based encoding converges faster and finds lower‑cost schedules.
• Open‑source implementation using the JGAP Java GA library, including a “SuperGene” validity‑check layer that can be reused in other scheduling contexts.
• Evidence that GA outperforms gradient‑based/analytical approaches for non‑differentiable, constraint‑heavy scheduling problems.

Methodology

1. Problem formulation –

   • Inputs: a list of tasks, each with a processing time, unit cost, and precedence list; a maximum allowed cycle time per station; unlimited stations.
   • Goal: minimize total cost, defined as the sum over stations of a function that combines the tasks’ unit costs and the station’s idle time (the gap between total task duration and the cycle‑time bound).

2. Chromosome encoding

   • Station‑based: a chromosome is an ordered list of “stations”; each station contains a variable‑length list of tasks. Validity is checked by a custom SuperGene class that rejects any station violating the duration bound or precedence rules.
   • Task‑based: a fixed‑length chromosome where gene i stores the station index for task i. This representation makes it trivial to enforce precedence (by checking the assigned stations) and the duration bound (by aggregating task times per station).

3. GA operators – Standard GA mechanisms are tweaked:

   • Crossover swaps subsequences of stations (station‑based) or exchanges station assignments for subsets of tasks (task‑based).
   • Mutation randomly reassigns a task to a different station, followed by a repair step to keep the schedule feasible.
   • Selection uses tournament selection to balance exploration and exploitation.
   • Replacement keeps the best individuals (elitism) while discarding the worst, ensuring steady improvement.

4. Experimental setup – Three synthetic precedence graphs (tight, loose, none) with varying numbers of tasks (10–50) were generated. Each GA variant ran for a fixed number of generations, and the best schedule cost was recorded.

Results & Findings

• Task‑based encoding consistently found cheaper schedules and required fewer generations to stabilize.
• For tightly coupled precedence graphs (many constraints), the advantage of task‑based encoding grew larger because the search space shrinks dramatically, and the encoding naturally respects constraints.
• The GA outperformed a simple linear programming relaxation and a handcrafted heuristic, especially when the cost function included non‑linear idle‑time penalties.

Practical Implications

• Plug‑and‑play scheduling engine – The JGAP‑based implementation can be wrapped as a microservice or library, letting factories feed task lists and receive cost‑optimal station assignments without reinventing the GA logic.
• Scalable to real‑world lines – Because the algorithm assumes an unlimited number of stations, it can be used to evaluate “what‑if” scenarios (e.g., adding a new workstation) and to compute the marginal cost of expanding capacity.
• Rapid prototyping for custom cost models – The cost function is modular; developers can inject their own penalty terms (energy consumption, labor overtime, equipment wear) and let the GA handle the combinatorial explosion.
• Integration with Industry 4.0 pipelines – The GA can run offline to generate baseline schedules, then be combined with real‑time dispatchers that adjust assignments on the fly when disruptions occur.
• Educational value – The side‑by‑side comparison of two encodings serves as a concrete case study for developers learning how representation choices dramatically affect evolutionary algorithm performance.

Limitations & Future Work

• Assumes unlimited stations – Real factories have a fixed number of workstations; extending the model to a hard station‑count constraint would require additional penalty or repair mechanisms.
• Synthetic benchmarks only – The experiments use generated precedence graphs; validation on actual shop‑floor data (e.g., automotive assembly lines) is needed to confirm robustness.
• Scalability ceiling – While the task‑based GA handled up to ~50 tasks comfortably, larger lines (hundreds of tasks) may demand parallel GA implementations or hybrid approaches (e.g., memetic algorithms).
• Cost function simplicity – The current cost model aggregates unit costs and idle‑time penalties; future work could incorporate stochastic processing times, maintenance windows, or multi‑objective trade‑offs (cost vs. throughput).

By exposing a clear, developer‑friendly GA framework for a notoriously hard scheduling problem, this research opens the door for smarter, cost‑aware production planning tools that can be integrated directly into modern manufacturing software stacks.

Authors

• Alireza Rezaee

Paper Information

• arXiv ID: 2601.00689v1
• Categories: cs.NE, cs.LG
• Published: January 2, 2026
• PDF: Download PDF