A Biased Random-Key Genetic Algorithm for Parallel Machine Scheduling with Precedence Constraints

The advancement of Industry 4.0 demands highly efficient production scheduling and resource optimization. In early industrial settings, task organization and scheduling decisions were often performed manually, relying on trial-and-error procedures or exhaustive enumeration. However, with the increasing complexity of production environments and the availability of advanced computational tools, the Task Scheduling Problem (TSP) has evolved into a central topic in operations research. This paper addresses the task sequencing problem in industrial environments, a notoriously complex NP-hard combinatorial optimization challenge. Specifically, we tackle the scheduling of jobs on identical parallel machines subject to precedence constraints, with the primary objective of minimizing the total production time, or makespan. We propose a robust solution approach utilizing the Biased Random-Key Genetic Algorithm (BRKGA) metaheuristic. The core of our methodology is a customized decoder that efficiently translates chromosome random keys into a task priority sequence. This sequence is then allocated using a constructive heuristic based on the Earliest Finish Time (EFT) criterion. Comprehensive computational experiments, including parameter sensitivity analysis and scalability tests on instances of up to 240 tasks, demonstrate that the proposed BRKGA configuration is highly stable and consistently capable of finding high-quality solutions for this problem.