Scheduling Optimization in Remanufacturing Systems

Problem Description

The Three-Stage Remanufacturing System Scheduling Problem (3T-RSSP) is a combinatorial optimization problem that aims to determine the processing sequence for a set of products to minimize the total completion time, known as makespan. This problem belongs to the family of Flow Shop Scheduling Problems (FSSP).

The system is structured in three consecutive stages:

1. Disassembly: Multiple End-Of-Life (EOL) products are processed on unrelated parallel machines, where each machine may have different processing times for the same product.
2. Reprocessing: The components resulting from disassembly go through dedicated reprocessing lines, which operate as a flow shop.
3. Reassembly: Finally, the reprocessed components are assembled back into a “like-new” product on parallel machines.

The problem is NP-hard, requiring advanced heuristic strategies to find high-quality solutions in reasonable computation times for real-world instances.

Industrial Context

Optimizing remanufacturing systems is a key task in advancing toward circular economy models and a more sustainable future. By returning EOL products to a functional state, the demand for raw materials, energy consumption, and waste generation are reduced.

This approach directly aligns with the United Nations’ Sustainable Development Goals (SDG) 9 (Industry, Innovation, and Infrastructure) and 12 (Responsible Consumption and Production). The 3T-RSSP has practical applications in sectors such as the automotive, aerospace, and wind turbine industries.

Common Challenges

• NP-Hard Nature: The computational complexity of the problem makes exact methods unfeasible for medium or large-sized instances.
• Hybrid Configuration: The problem combines features from different scheduling environments, such as the Hybrid Flow Shop (with multiple parallel machines) and Unrelated Parallel Machine Scheduling (machines with different processing speeds).
• Inter-Stage Dependency: The schedule of one stage directly impacts the start and end times of subsequent stages, creating strong interdependencies that must be managed.
• Component Coordination: It is necessary to ensure that all components of a single product have been reprocessed before its final assembly can begin.

Solution Approaches

To efficiently solve the 3T-RSSP, your work proposes the use of a GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic. This method stands out for its excellent balance between solution quality and computation time. The implementation consists of an iterative process with two main phases:

1. Constructive Phase: A high-quality initial solution is generated through a procedure that combines a greedy function (based on the partial makespan) with a random component to explore different areas of the solution space.
2. Local Search: The constructed solution is improved by exploring an extended neighborhood, generated from two types of moves: insertion and interchange of products within the sequences of each stage.

This approach has proven to be highly competitive, obtaining high-quality results on a set of 34 state-of-the-art instances while reducing computation time by two orders of magnitude compared to other methods.

References

1. Diaconescu, T. A., Herrán, A., & Colmenar, J. M. Un algoritmo GRASP para el sistema de remanufactura en tres etapas. Submitted to XVI Congreso Español de Metaheuristicas, Algoritmos Evolutivos y Bioinsiprados (MAEB 2025).
2. Wang, W. et al. (2024). Mixed-integer linear programming and composed heuristics for three-stage remanufacturing system scheduling problem. Engineering Applications of Artificial Intelligence, 137, 109257.
3. Wang, W. et al. (2024). More mixed-integer linear programming models for solving three-stage remanufacturing system scheduling problem. Computers & Industrial Engineering, 194, 110379.
4. Kim, M.G., Yu, J.M., & Lee, D.H. (2015). Scheduling algorithms for remanufacturing systems with parallel flow-shop-type reprocessing lines. International Journal of Production Research, 53(6), 1819-1831.
5. Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205(1), 1-18.

Acknowledgments

This summary was prepared by the RedHEUR4.0 network as part of its contribution to the digital transformation of the transportation and logistics sectors, supported by the Spanish Ministry of Science and Innovation.