NEH Heuristic Minimizes Makespan in Aerospace Flow Shop Scheduling Under Variable Workloads

In aerospace manufacturing facilities where intricate component routing, tight precision tolerances, and volatile machine workloads converge, optimizing operational sequencing remains essential to prevent severe downstream assembly delays. A computational study published in Discover Mechanical Engineering evaluated three prominent flow-shop scheduling heuristics—the Nawaz-Enscore-Ham algorithm, the Campbell-Dudek-Smith technique, and the Palmer Slope Index—alongside an incremental learning fast surrogate-assisted evolutionary algorithm. Analyzing an industrial dataset from aircraft manufacturer DI involving the machining of twenty aircraft wing components across thirteen successive machine tools, the researchers determined that Nawaz-Enscore-Ham achieved the lowest overall makespan, completing all operations in approximately 46.029 hours. This performance edge was particularly pronounced across manufacturing environments characterized by substantial processing-time variance and unequal workload distributions among sequential workstations.

The scheduling challenge addressed by the research group, led by Pradeep Yadav, Madan Jagtap, Prasad Karande, and Prasad Bari, stems directly from operational complications documented in commercial aerospace manufacturing. At manufacturer DI, delivery schedules for A380 aircraft wing subassemblies encountered major disruptions in 2017 because components stalled during multi-stage machining processes. In flow-shop manufacturing systems, every workpiece must progress through an identical sequence of workstations, but individual processing times vary drastically across different stages. Without optimized sequencing, workpieces accumulate in staging buffers before bottleneck machinery while subsequent stations sit idle, inflating the total completion duration known as the makespan and cascading delays into final assembly.

To rigorously assess scheduling performance, the researchers constructed a computational framework modeling a twenty-job, thirteen-machine permutation flow shop based on the industrial case study. In this configuration, each component, designated Job 1 through Job 20, required specific, highly variable processing durations across thirteen machines labeled M1 through M13. For instance, processing Job 1 required 0.13 hours on the initial machine, 0.77 hours on the second, and 2.26 hours on the third machine, illustrating the uneven operational burdens distributed across the plant floor. Processing times recorded across all twenty jobs showed extreme heterogeneity, demanding algorithms capable of mitigating idle time without requiring impractical computation times.

To make the algorithmic solutions accessible to factory decision-makers without requiring specialized programming skills, the research team developed an automated Python-based graphical user interface. The interactive system ingests the raw job-machine processing time matrices, executes the heuristic sequencing algorithms, and generates visual schedules alongside Gantt charts and makespan comparison plots in real time. In an initial baseline demonstration using four jobs routed across three machines, the interface demonstrated how heuristic rules allocate machine capacity over time. For that four-job trial, both Nawaz-Enscore-Ham and Palmer Slope Index produced a minimum makespan of 35 time units with schedules such as Job 3 to Job 1 to Job 2 to Job 4, whereas the Campbell-Dudek-Smith approach generated a sequence yielding 41 time units.

When applied to the primary industrial case study of twenty aerospace wing components, the Nawaz-Enscore-Ham heuristic demonstrated superior optimization capability. The algorithm operates on the principle of constructive insertion: it first sums the operational durations of each job across all thirteen workstations and ranks them in descending order of total work content. In the aerospace dataset, Job 16, Job 15, and Job 20 exhibited the highest cumulative machining requirements, forming the initial sorting order. The algorithm then builds the production schedule iteratively by placing each subsequent job into every possible position within the partial sequence and retaining the specific permutation that yields the lowest intermediate makespan. Following this progressive insertion mechanism, Nawaz-Enscore-Ham identified the sequence 18-5-13-3-9-1-6-16-14-19-17-8-20-15-12-4-10-2-11-7, achieving the best makespan of 46.029 hours.

The Campbell-Dudek-Smith heuristic performed nearly as effectively as Nawaz-Enscore-Ham on the aerospace benchmark, concluding with a final makespan of 46.03 hours. Campbell-Dudek-Smith adapts Johnson’s classic two-machine sequencing rule to multi-machine environments by aggregating operational times into a series of pseudo-two-machine problems across twelve distinct stages. In Stage 1, using only processing times from the first machine and the thirteenth machine, the algorithm established an initial sequence of 2-4-17-3-7-19-13-5-8-20-15-11-6-16-12-1-14-10-9-18 that resulted in a makespan of 48.1 hours. Aggregating times across the first two and final two machines in Stage 2 refined the sequence to 19-6-7-17-18-11-12-20-13-15-10-9-8-16-5-4-3-1-14-2, lowering the makespan to 47.8 hours. By progressing through all successive machine aggregations, the method eventually identified the optimal schedule 13-6-5-3-10-4-9-1-7-8-18-11-14-19-17-2-20-12-15-16, successfully reaching 46.03 hours.

In contrast, the Palmer Slope Index produced a somewhat less compact schedule for the twenty aerospace parts, generating a final makespan of 46.5 hours. Palmer Slope Index functions by computing a single weighted numerical slope index for each job, assigning higher weights to processing stages that occur earlier in the workstation chain. By arranging jobs in ascending order of their calculated slope values, the method produced the sequence 13-18-6-9-19-10-5-8-20-17-3-4-7-11-1-14-15-12-16-2. Although Palmer Slope Index is computationally straightforward and executable even without extensive computational resources, its reliance on fixed weighting factors leaves it vulnerable to machine-specific congestion when processing durations fluctuate irregularly across intermediate stations.

The study also evaluated an advanced multi-objective optimization method: a Fast Surrogate-Assisted Evolutionary Algorithm based on incremental learning using neural network approximations. Designed to address computationally intensive optimization challenges, the surrogate model screens candidate schedules before conducting full fitness evaluations on select sequences. When executed on the twenty-job, thirteen-machine dataset, this evolutionary approach produced an optimal sequence of 18-3-10-9-4-1-8-16-13-14-19-17-5-6-20-15-12-2-11-7, achieving a minimum makespan of 46.03 hours. This outcome matched the 46.03-hour makespan achieved by the Campbell-Dudek-Smith heuristic, confirming that well-designed classical heuristics can match the solution quality of complex surrogate-assisted evolutionary searches for flow-shop makespan minimization.

To formalize these findings into industrial guidance, the authors synthesized their comparative observations into a condition-based heuristic performance framework. Rather than assuming that a single scheduling rule is universally optimal, the framework maps algorithm selection to explicit operational variables, including processing-time variability, machine counts, and workload imbalance across stations. In manufacturing systems, workload imbalance reflects the proportional difference between maximum and minimum station loads relative to plant-wide averages. The evaluation showed that Nawaz-Enscore-Ham demonstrates very low sensitivity to severe workload imbalances because its progressive insertion logic naturally accommodates overloaded machines, making it the preferred choice for complex, high-mix aerospace production. Conversely, Campbell-Dudek-Smith shows moderate sensitivity and remains highly competitive for medium-scale structured facilities requiring fast turnaround, while Palmer Slope Index is best reserved for smaller, stable shops with low variance.

The authors noted that their empirical findings remain grounded within deterministic processing times derived from the twenty-job, thirteen-machine aerospace wing manufacturing case study. Because real-world factory floors encounter unforeseen disturbances such as machine breakdowns, sudden urgent orders, and dynamic maintenance intervals, the researchers highlighted the need for future investigations. Prospective extensions include incorporating energy consumption and carbon emissions into multi-objective models, integrating hybrid metaheuristics such as genetic algorithms or ant bee colony optimizations, and developing real-time rescheduling mechanisms to strengthen operational resilience under dynamic industrial conditions.

Subject of Research: Heuristic flow-shop scheduling algorithms for makespan minimization in aerospace manufacturing under variable workloads

Article Title: Dynamic heuristic scheduling for aerospace flow-shop manufacturing under variable workloads

Article References: Yadav, P., Jagtap, M., Karande, P., & Bari, P. (2026). Dynamic heuristic scheduling for aerospace flow-shop manufacturing under variable workloads. Discover Mechanical Engineering, 5(1), Article 217. https://doi.org/10.1007/s44245-026-00415-4

Image Credits: AI Generated

DOI: 10.1007/s44245-026-00415-4

Keywords: aerospace manufacturing, flow-shop scheduling, makespan minimization, Nawaz-Enscore-Ham, Campbell-Dudek-Smith, Palmer Slope Index, workload variability, permutation flow shop, computational scheduling, manufacturing operations, aircraft wing production, heuristic optimization, job sequencing, industrial engineering, decision support systems, surrogate-assisted evolutionary algorithms