Multi-Objective Identical Parallel Flow Shop Scheduling Using NSGA-II and MOPSO with a Novel Load Balancing Procedure

2.1 Existing methods and models

Most existing studies in flow shop and parallel flow shop scheduling adopt single-objective formulations, primarily focusing on makespan minimization due to its mathematical tractability and long-standing use as a benchmark in scheduling research. A comparative simulation study was conducted to evaluate production scheduling strategies in hybrid and parallel flow shop environments using the General Shifting Bottleneck Routine (SBR). The study assessed the effectiveness of several dispatching rules, including First Come First Served (FCFS), Longest Processing Time (LPT), and Shortest Processing Time (SPT), in managing workflow and improving throughput [13]. Complementing this line of research, a multi-phase heuristic algorithm was developed, comprising a constructive heuristic for initial job sequencing and an improvement heuristic aimed at balancing workloads by exchanging jobs between production lines [14].

Building on prior work, subsequent studies introduced methodological advancements centered on approximation techniques. One study proposed a 3/2-approximation algorithm for scheduling jobs in a two-stage parallel flow shop with multiple identical machines. A 12/7-approximation algorithm was also developed for a three-stage configuration [15]. Subsequently, a pseudo-polynomial time dynamic programming algorithm was introduced to generate exact solutions. This algorithm served as a core subroutine in constructing a Fully Polynomial-Time Approximation Scheme (FPTAS) [16]. In a related study, the FPTAS was further refined by classifying jobs into large and small categories. Schedules for large jobs were enumerated, while small jobs were allocated using a linear programming model combined with a sliding window technique [17]. In a later enhancement, the FPTAS was extended by scaling arbitrary instances into restricted forms and solving them using a Mixed-Integer Linear Programming (MILP) model, resulting in near-optimal solutions with bounded approximation errors [18].

Recently, Ribas et al. [7] conducted several studies focusing on the Parallel Flow Shop Scheduling Problem (PFSSP) under blocking constraints. The initial work introduced the use of Iterated Local Search (ILS) and Iterated Greedy Algorithm (IGA), integrated with two types of Variable Neighborhood Search (VNS), in conjunction with constructive and improvement heuristics. A MILP model was also proposed for solving small-scale instances. In subsequent work, an Iterated Greedy (IG) algorithm was developed, beginning with a high-quality initial solution and refining it through perturbation and local search, using a simulated annealing-based acceptance criterion to escape local optima [8]. More recently, 36 constructive heuristics were evaluated, combining seven sequencing rules with five lines allocation methods. From this set, the RCP0 heuristic was proposed, prioritizing the line with the earliest available machine and the job that minimizes machine idle time [6].

Some studies have addressed other alternative objectives using diverse heuristic and optimization techniques. In another study, total tardiness was minimized using an Iterated Greedy Algorithm (IGA), which enhanced initial solutions through Variable Neighborhood Search (VNS) and job reassignment mechanisms [19]. Additionally, total flow time was targeted through the application of priority rule-based heuristics, the NEH algorithm, and IGA to obtain near-optimal schedules [20].

Multi-objective optimization aligns more closely with practical manufacturing needs by simultaneously optimizing conflicting performance criteria. A simheuristic algorithm was proposed for stochastic, non-Identical Parallel Flow Shop Scheduling, integrating a biased-randomized NEH heuristic, local search, and Monte Carlo simulation to evaluate deterministic and expected makespan values [21]. Another study addressed the bicriteria objective of minimizing total earliness and tardiness using a hybrid approach that combines a Greedy Randomized Adaptive Search Procedure (GRASP) with Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), demonstrating superior performance over individual strategies [22]. A further contribution focused on minimizing total flow time and the number of tardy jobs in a two-machine, non-identical parallel flow shop. The proposed Multi-Objective Evolutionary Algorithm (MOEA) incorporated local search into the NSGA-II framework, proving more effective and efficient than conventional MOEAs [23].

Task sequencing has long been a cornerstone of flow shop scheduling research, with foundational works such as Johnson’s (1954) rule for two-machine optimization [24], the Nawaz-Enscore-Ham (NEH) algorithm (1983) for permutation flow shops [25], and the Campbell-Dudek-Smith (CDS) method (1970) for multi-machine scheduling establishing key heuristics [26]. Over time, substantial progress has been made in addressing sequencing under complex constraints, particularly in dynamic and data-driven manufacturing environments. Recent studies reflect a shift toward intelligent, adaptive methods. One approach applies deep reinforcement learning (DRL) to dynamic parallel machine scheduling, using a modified Transformer model and a variable-length state matrix to capture job and machine data. The DRL agent autonomously extracts features and selects jobs for idle machines to improve scheduling performance [27]. Another study builds on the NEH algorithm, adapting it for the satellite industry by sorting jobs based on processing times and enhancing it with a discrete-event simulation model that reflects real workshop conditions, improving both adaptability and practicality [28]. Another study introduces a dynamic knowledge graph to represent distributed manufacturing resources, combined with an AI scheduler trained through DRL and optimized using a dueling Deep Q-Network (DQN). Semantic matching aligns resources with subtasks, while meta-heuristic methods support near-optimal scheduling decisions [29].

Despite advances in task sequencing, load balancing is still underdeveloped in manufacturing. Most current approaches rely on static or predefined job-to-line assignments, leading to workload imbalances. In contrast, domains like cloud computing have advanced adaptive load balancing techniques to address similar challenges. Recent studies have explored intelligent optimization methods to enhance task scheduling and resource allocation. One approach uses deep learning models, specifically Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs), to cluster virtual machines (VMs) into overloaded and underloaded groups. It combines Reinforcement Learning with a Hybrid Lyrebird Falcon Optimization (HLFO) algorithm, which merges Lyrebird and Falcon Optimization strategies to improve system performance [30]. Another hybrid model, QMPSO, integrates Modified Particle Swarm Optimization (MPSO) with improved Q-learning, adjusting MPSO’s velocity based on Q-learning policies to balance VM loads and optimize resource use [31]. Similarly, Load Balancing Modified PSO (LBMPSO), a tailored variant of PSO, updates fitness values and tracks particle positions while continuously monitoring VM loads for efficient task assignment [32].

2.2 Research gaps and study motivations

A review of parallel flow shop scheduling literature reveals several key research gaps:

Current research remains heavily focused on single-objective formulations, with a predominant emphasis on makespan minimization. While this objective offers mathematical tractability and benchmarking consistency, it fails to capture the multi-dimensional trade-offs encountered in real-world manufacturing. Multi-objective models are significantly underexplored in IPFSSP contexts.

The prevailing focus on proportional parallel flow shop configurations limits the generalizability of many existing approaches. In these systems, job-to-line assignment is often simplified by performance asymmetries across lines. However, this assumption does not apply in identical configurations, where all lines have uniform capabilities. Effective job allocation in such systems requires more sophisticated load balancing strategies.

Challenges related to heterogeneous job priorities in identical parallel flow shops remain insufficiently addressed. The absence of line hierarchies and the mix of critical and non-critical tasks increase scheduling complexity. These conditions highlight the need for adaptive, real-time load balancing mechanisms.

Existing load balancing strategies in IPFSSP are typically static or heuristic-based and lack the flexibility to respond to system dynamics. This rigidity often results in inefficient resource utilization and the emergence of operational bottlenecks.

The scheduling literature continues to prioritize task sequencing, often treating it independently from job-to-line assignment. This separation creates fragmented decision-making, despite growing evidence that integrated approaches yield more balanced and efficient schedules in identical parallel environments.

Cross-disciplinary knowledge transfer between cloud computing and manufacturing scheduling remains limited. Proven concepts from computing—such as decentralized load balancing and adaptive resource allocation—are rarely applied in production scheduling, despite their relevance.

In response to these gaps, this study proposes a novel dynamic load balancing strategy embedded within NSGA-II and MOPSO frameworks, specifically designed for multi stage identical parallel flow shop systems. The approach jointly optimizes job-to-line assignment and sequencing while minimizing makespan and total earliness–tardiness, under inter-machine waiting time constraints.

This section presents the methodological framework developed to address the proposed scheduling problem.

4.1 Load Balancing Procedure (LBP)

The Load Balancing Procedure (LBP) is a multi-phase scheduling heuristic specifically designed to address the load imbalance problem in parallel flow shop environments with multiple machines per line. It aims to minimize the makespan and total earliness/tardiness while strictly enforcing a maximum wait time constraint before job processing begins. The procedure starts by evaluating each job’s criticality score, derived from processing time and slack, to prioritize urgent and resource-intensive jobs. This phase has a time complexity of $O(n \log n+n . L . m)$, accounting for criticality scoring, sorting, and constraint-aware assignment. The remaining non-critical jobs are then distributed to balance the load across all lines, with a complexity of $O(n . L)$, based on comparative workload evaluation across lines. A final feasibility repair phase reorders and adjusts job start times to ensure full compliance with the wait time constraint; this step involves resequencing within lines and has a worst-case complexity of $O\left(L . n^2 . m\right)$. Overall, the LBP achieves efficient and constraint-aware scheduling with an upper-bound complexity of $O\left(L \cdot n^2 \cdot m\right)$, ensuring computational scalability for large, constrained production environments and demonstrating strong practical applicability in real-world industrial systems characterized by high complexity and scale. The steps of the proposed procedure are detailed in the pseudo code shown in Table 2.

Table 2. Pseudo-code for proposed LBP

4.2 Integration with MOO algorithms

In the proposed approach, the Load Balancing Procedure (LBP) is embedded within both NSGA-II and MOPSO as a constraint-aware decoding mechanism. In NSGA-II, LBP is applied during the fitness evaluation steps, specifically in Step 2 to decode each randomly generated individual in the initial population, and Step 6 to evaluate the offspring population after crossover and mutation. Similarly, in MOPSO, LBP is applied in Step 2 to evaluate the initial swarm and in Step 7 to assess each particle after position updates. In both algorithms, LBP constructs feasible schedules by assigning jobs to parallel production lines while enforcing the maximum wait time constraint ($W \max$) and then computes the makespan and total earliness/tardiness to form the objective vector. As shown in Figure 1, this consistent application of LBP ensures that all candidate solutions, regardless of their origin, are decoded into valid, constraint-compliant schedules. This enables both NSGA-II and MOPSO to maintain feasibility throughout the search process and effectively converge toward well-distributed, Pareto-optimal fronts in the solution space.

1.png

Figure 1. Flowcharts of enhanced algorithms

4.3 Taguchi method for parameter tuning

The Taguchi Method, developed by Dr. Genichi Taguchi, employs orthogonal arrays and signal-to-noise (S/N) ratios [33], to systematically optimize algorithm parameters, S/N ratios were computed using the smaller-the-better formula $\left(-10 \log _{10}\left(\frac{1}{n} \sum y_i^2\right)\right)$ to align with our minimization objectives. Sensitivity analysis using $(\Delta S / \mathrm{N}=\max -\min)$ revealed that mutation type had the strongest influence on Enhanced NSGA-II-LBP performance, with swap operations outperforming other operators by 9.9%. Population size and crossover type also showed notable effects, while crossover probability had a comparatively limited impact.

For the Enhance MOPSO-LBP algorithm, the specific configuration of the nGrid parameter demonstrated the highest level of influence among all the factors that were evaluated. In particular, the finer settings—specifically those set at values of 0.1, 5, and 3.0—were observed to significantly improve the overall algorithm performance, resulting in a measurable enhancement of approximately 25 to 26 percent. Additionally, the adjustment of velocity limits, as well as the cognitive coefficient, also exhibited considerable influence on the behavior and outcomes of the algorithm. In contrast, however, the social coefficient consistently showed much weaker sensitivity throughout the testing process, which was notably contrary to our initial expectations and earlier assumptions.

Table 3 summarizes optimal parameters for NSGA-II variants, with sensitivity rankings confirming the critical role of mutation type. Enhanced NSGA-II requires a larger population size (100 vs. baseline 80) to improve Pareto front coverage, higher crossover probability (0.9 vs. 0.85) to maintain diversity under workload imbalance, and swap mutation to preserve schedule feasibility, structural choices proving more impactful than probability tuning. PMX crossover and tournament selection maintained consistent superiority across configurations, though with moderate sensitivity. Table 4 outlines Enhanced MOPSO's settings, where sensitivity analysis justified larger swarm sizes (100 vs. 80) for solution diversity, elevated inertia weight (0.75 vs. 0.45) for exploration balance, expanded velocity limits (12 vs. 10) to reduce machine idle time, and stronger cognitive coefficient (c₁=1.1) for particle coordination.

Table 3. Optimal parameters for NSGA-II and enhanced NSGA-II

Table 4. Optimal parameters for MOPSO and enhanced MOPSO

Figure 2 represents main effects plots visually corroborate these findings through slope steepness.

2.png

2.png

Figure 2. Main effects plot for S/N ratios of each algorithm

Figure 3 presents the performance distributions across four key metrics NPS, HV, IGD and Δ, comparing baseline algorithms with their enhanced counterparts.

3.png

Figure 3. Boxplots of comparative performance metrics

1. Number of Pareto Solutions (NPS): Enhanced NSGA-II generates 40–70% more non-dominated solutions than the baseline (5.8–10.5 vs. 3.5–7.6), while enhanced MOPSO achieves a 40–50% increase (5.2–10 vs. 3.5–7.3). This indicates that both improved algorithms sustain significantly larger and more diverse Pareto sets. A strong negative correlation with IGD (r = –0.92 for NSGA-II-LBP; r = –0.94 for MOPSO-LBP) further confirms that increased diversity contributes to better convergence.
2. Hypervolume (HV): Both enhanced algorithms show a 30–35% increase in HV compared to their respective baselines (0.41–0.84 vs. 0.30–0.65 for NSGA-II; 0.37–0.78 vs. 0.28–0.59 for MOPSO), reflecting stronger convergence–diversity performance. This is supported by a strong negative correlation with IGD (r = –0.93), indicating that broader coverage of the Pareto front coincides with closer proximity to the true front.
3. Inverted Generational Distance (IGD): Enhanced NSGA-II and MOPSO achieve IGD reductions of 45–65% and 40–65%, respectively, indicating significant gains in convergence (e.g., 3.88–6.35 vs. 7.31–18.41 for NSGA-II; 4.10–7.30 vs. 6.68–20.58 for MOPSO). A strong positive correlation with Spread (r = 0.89 for NSGA-II-LBP; r = 0.91 for MOPSO-LBP) reveals that convergence improvements are accompanied by more uniform solution distributions.
4. Spread (Δ): LBP reduces Spread by 10–25%, with NSGA-II-LBP ranging from 0.26–0.49 (vs. 0.35–0.55) and MOPSO-LBP from 0.28–0.50 (vs. 0.38–0.56). This reflects improved distribution uniformity, essential for balanced scheduling. A strong negative correlation with HV (r = –0.85 for NSGA-II-LBP; r = –0.88 for MOPSO-LBP) confirms that uniformity enhances coverage quality.

The correlation coefficients were calculated based on Spearman’s rank correlation approach, as presented in Eq. (14):

$\rho=1-\frac{6 \sum d_i^2}{n\left(n^2-1\right)}$          (14)

These relationships highlight LBP’s ability to reconcile historically conflicting objectives. The strong HV–IGD correlation (r ≈ –0.93) confirms that convergence and coverage improve jointly, driven by LBP’s criticality scoring, which selects jobs that enhance both. The positive IGD–Δ correlation (r > 0.89) reflects LBP’s capacity to produce evenly distributed, high-quality solutions through constraint-aware sequencing. Finally, the weak NPS–Δ correlation (r ≈ –0.40) demonstrates that diversity and distribution can improve concurrently a direct result of LBP’s two-phase structure, which decouples job selection from load balancing.

Together, these findings confirm that the proposed approach resolves the convergence, diversity, and distribution trade-off, offering a coherent multi-objective optimization framework for complex scheduling environments.

The Pareto front visualization in Figure 4 provides valuable insight into solution quality for the 50_20 instance, illustrating how the proposed heuristic enhancements reshape the distribution of trade-offs between makespan and earliness–tardiness. Enhanced NSGA-II achieves the most balanced compromise, delivering solutions particularly well-suited for practical scheduling environments where both efficiency and due-date compliance are critical. These solutions reflect marginal trade-offs, making them highly operationally relevant. Enhanced MOPSO follows closely, also achieving a balance between objectives, though with a slight preference toward minimizing makespan. Collectively, the enhanced algorithms expand the Pareto front by 31.5% in hypervolume compared to baseline methods, indicating broader solution diversity and improved exploration of extreme trade-offs. The Pareto front of the enhanced methods forms a clear convex shape, reinforcing the soundness of the proposed Load Balancing Procedure (LBP).

4.png

Figure 4. Pareto front for instance 50_20

Figure 5 presents a comparative analysis of makespan and total earliness/tardiness performance. Figure 5(a) illustrates makespan values, while Figure 5(b) displays total earliness/tardiness. The results in Figure 5(a) confirm that Enhanced NSGA-II-LBP achieves an average makespan reduction of 19.2% relative to conventional NSGA-II, with improvements reaching 28.9% in large-scale instances (e.g., Instance 20_20_10: 1667 → 1350). These gains are consistent across complexity levels, ranging from 8.3% to 28.9%. In parallel, Enhanced MOPSO-LBP yields an average makespan reduction of 13.7%, with peak improvements of 22.4% (e.g., Instance 50_20_8: 2518 → 2191), and a tighter performance spread (3.1% to 22.4%), reflecting uniform scalability.

5.png

Figure 5. Comparative analysis of makespan and total earliness/tardiness

Figure 5(b) highlights similar trends for total earliness/tardiness. Enhanced NSGA-II-LBP achieves a 22.8% average reduction, with maximum gains of 39.2% in high-tardiness scenarios (e.g., Instance 50_20_5: 2421 → 2058), underscoring its strength in mitigating due-date violations through effective load balancing. Likewise, Enhanced MOPSO-LBP provides a robust 18.4% reduction, with peak improvements of 38.2% (e.g., Instance 50_20_6: 2462 → 2191), and demonstrates consistent performance across instance groups. These results emphasize the benefits of LBP integration in both algorithms, offering notable improvements in convergence quality and scheduling stability.

The runtime analysis CPU (Central Processing Unit) in Figure 6 reveals Enhanced NSGA-II and NSGA-II exhibit comparable computational times (1.1–2.8 seconds), indicating minimal overhead from the load-balancing heuristic. MOPSO consistently outperforms both NSGA-II variants, with 30–50% faster execution (e.g., 0.484–1.588 vs. 1.1–2.8 seconds for NSGA-II), attributed to swarm-based parallelism. Enhanced MOPSO incurs a marginal runtime increase over MOPSO (e.g., 0.614–1.792 vs. 0.484–1.786 seconds). Notably, all algorithms scale linearly with instance complexity (e.g., 20_05: ~1.1 seconds; 50_20: ~2.8 seconds), but MOPSO’s lower absolute times highlight its suitability for real-time scheduling.

6.png

Figure 6. Comparative CPU time

6.1 Algorithm comparison

This demonstrative example, shown in Figure 7, is based on a small instance of three parallel flow shop lines, each with five machines and a total of 21 jobs. The Gantt charts illustrate the impact of the Load Balancing Procedure (LBP) on job scheduling. Figure 7(a) represents the schedule generated by Enhanced NSGA-II, while Figure 7(b) corresponds to the baseline NSGA-II.

7.png

7.png

Figure 7. Gantt chart comparison of NSGA II–LBP and NSGA-II

In Figure 7(a), all three lines exhibit compact, well-coordinated job sequences, with operations tightly packed across machines. Final operations complete near a unified makespan threshold (~800), as indicated by the red dashed line, reflecting effective synchronization and load balancing. In contrast, Figure 7(b) displays fragmented scheduling with visible idle gaps and poor load distribution, particularly in Flow Shop Lines 2 and 3, where machine inactivity extends the makespan beyond 890. The rightward-pointing dashed arrows highlight delays in completing final operations. Furthermore, job sequencing lacks continuity, resulting in inefficient resource utilization and disrupted flow. Final job completion times vary substantially across lines, ranging from 600 to nearly 900, indicating a significant imbalance. This discrepancy results in early completions on some lines, leading to premature inventory and delays on others, ultimately compromising overall schedule stability.

Figure 8 illustrates the load distribution performance of the enhanced algorithms across three identical parallel production lines. Both enhanced approaches produce tightly clustered workload values (e.g., Enhanced NSGA-II: [771.5, 757.5, 757.5]; Enhanced MOPSO: [854.0, 830.5, 819.0]), with inter line variance remaining below 5%. This outcome reflects the effectiveness of the integrated heuristic in achieving balanced utilization across resources. In contrast, the baseline algorithms exhibit pronounced disparities in workload allocation (e.g., NSGA-II: [484.5, 417.5, 258.5]; MOPSO: [1250, 1625, 1300]), with deviations exceeding 40–60%, thereby highlighting the limitations of conventional methods in achieving load balance.

8.png

Figure 8. Comparison of load distribution between enhanced and conventional algorithms

6.2 Statistical validation

To evaluate the effectiveness of the proposed heuristic enhancements, statistical analyses were performed using Analysis of Variance (ANOVA) and paired t-tests across multiple benchmark instances (Tables 6 and 7). The ANOVA results include partial eta-squared (η²) values and 95% confidence intervals (CIs) to quantify the effect size of algorithmic differences. Paired t-tests are further supported by Cohen’s d to indicate the magnitude of observed differences.

Table 6. ANOVA summury table

Table 7. Paired t-test results

Table 6 presents the ANOVA outcomes across all evaluated metrics. The p-values were consistently below 0.001, leading to the rejection of the null hypothesis of equal performance among algorithms. Large effect sizes (η² = 0.38–0.93) with tight confidence intervals suggest that algorithm choice substantially influences performance across benchmark instances. Notably, hypervolume (HV) and inverted generational distance (IGD) show strong discriminative power, with η² reaching 0.72 [0.67, 0.77] for IGD, indicating that the enhancements significantly improved convergence and diversity. The most pronounced values were observed for CPU time (η² > 0.83), reflecting measurable runtime differences due to the Load Balancing.

Following the ANOVA results, which decisively rejected the null hypothesis H₀, post-hoc paired t-tests were conducted to evaluate whether the mean performance of two related algorithmic approaches differs significantly. To control the family-wise error rate (FWER) arising from multiple comparisons, the Bonferroni correction was applied, adjusting the significance threshold, as in Eq. (15):

$\alpha_{\text {adjusted }}=\frac{\alpha_{\text {desired }}}{\text { number of comparisions }}=\frac{0.05}{6} \approx 0.0083$          (15)

As shown in Table 7, statistically significant results (α = 0.0083) are accompanied by large or very large effect sizes in most cases (|d| > 0.8). For example, Enhanced NSGA-II exhibited strong gains in solution quantity (NPS) over the baseline (Cohen’s d = 1.19–2.59), while Enhanced MOPSO achieved substantial reductions in CPU time compared to NSGA-II (d = –3.55 to –12.61). Differences between Enhanced MOPSO and its baseline were negligible (|d| < 0.2), confirming comparable efficiency. Enhanced NSGA-II also maintained similar computational times to its baseline, with small effect sizes (d = –0.27 to 0.99), suggesting the added procedures introduce only minor runtime variation.

Overall, these findings demonstrate that the proposed enhancements significantly improve solution quality across multiple objectives. While some increase in computational time is observed, the overall benefits in convergence, diversity, and robustness clearly outweigh the cost, particularly in applications where scheduling quality is a critical requirement.