In 1980, a graduate student from Pakistan, Muhammad Nawaz, was stuck on a problem that had been circling in his head for months: how to order a sequence of jobs — or tasks, as they are interchangeably used in scheduling literature — through a set of machines, or processors, so that nothing sat idle and nothing waited longer than it had to. Scheduling problems like this can quickly get out of control; adding just a few more jobs can cause the number of possible orderings to explode. Then something clicked. Muhammad Nawaz worked out a simple rule: rank the items by how much total work is required/demanded, then insert them one at a time, always in the slot that causes the least delay. He tested his heuristic again and again on problems he’d shelved as too messy to solve, and each time, the same rule found a strong answer in a fraction of the time older methods needed.
Nawaz turned his solution into a journal paper. The paper was published in 1983 in Omega – the International Journal of Management Science, alongside his supervisors, EE Enscore and I Ham; it introduced to the world what the scheduling discipline now calls the NEH algorithm. The acronym stands for Nawaz, Enscore, and Ham, named after the paper’s three authors.
In the four decades since, the paper has drawn more than 3,600 citations, and academic textbooks feature and lecturers teach the NEH algorithm worldwide. Spanish-language lectures on the method, for instance, are freely available online from Spain’s Universitat Politècnica de València2. Few ideas from a single graduate thesis get to say that. However, outside a small circle of industrial engineers and Operations Research practitioners, almost no one has heard of Muhammad Nawaz – a Pakistani.
The Man and His Work
Nawaz was born in Lahore, Pakistan, and completed his engineering degree in 1973 at the University of Engineering and Technology (UET) Lahore, one of the country’s most prestigious institutions. He went on to teach there before receiving a scholarship to pursue a master’s degree in industrial engineering at Pennsylvania State University. It was there that he came under the mentorship of Professor Enscore, whose influence Nawaz has credited heavily for shaping the research that would make his name.
In 1980, Nawaz returned to the University College of Engineering (now UET, Taxila), Pakistan. In 1986, he moved to Melbourne, Australia, where he spent 27 years at RMIT University, teaching, designing and managing several undergraduate and postgraduate courses as a Program Director. Now retired, he looks back on the reach of his work with evident pride: “The NEH algorithm is a globally recognized model and is still part of curriculum teaching scheduling techniques,” he said, noting it has been translated into several languages and is taught in universities across continents.
Unfortunately, NEH has yet to receive its due credit. Neither is it part of Pakistani universities’ curriculum, nor has Nawaz received any formal recognition in Pakistan for his work that now stands as a baseline in real industry settings and is built on a procedure that is easy to understand.
A Simple Idea That Solved a Hard Problem
The problem Nawaz tackled belongs to a category called NP-hard flow-shop scheduling: every job passes through the same machines in the same order, and the goal is to arrange the jobs so the whole batch finishes as fast as possible, a measure engineers call the “makespan.” The same shape shows up anywhere work has to move through fixed stations in sequence: a manufacturing plant, planes queued for a runway, patients moving through a hospital’s operating theaters.
More than four decades on, it still shows up in solutions for small to smart manufacturing plants, warehouses, military aviation units, and satellite communications systems.
How It Works
The NEH heuristic works in steps. First, it calculates the total processing time on all machines for each job. Then it sorts the jobs in descending order, so the longest job comes first. From there, it builds the final schedule incrementally: it takes the top two jobs and tests which arrangement produces the shortest makespan, then inserts each subsequent job into every possible position, front, middle, or end, keeping whichever placement minimizes the total time. It repeats this process until every job has a place in the sequence.
The Nawaz, Enscore, Ham algorithm is a “constructive” heuristic: it builds the schedule piece by piece, always favoring the option that shortens the makespan at every step. An analogy from distinguished Polish researcher Czesław Smutnicki compares it to packing a hiking backpack: “You start by placing the largest items first, testing how they fit together, then work in progressively smaller items, adjusting as you go.”
Factory Floor to AI
The NEH algorithm acts as the core baseline, merged with stronger hybrid algorithms to solve industrial-level problems. A 2023 study shows its precedence over other methods when solving a permutation flow shop scheduling problem under no-idle and setup-time constraints. It also acts as the seed sequence for high-performing metaheuristics like Genetic Algorithms (GA), Particle Swarm Optimization (PSO), and Artificial Bee Colony (ABC) methods6.
From manufacturers in Indonesia to the Netherlands, NEH-based scheduling reduces production makespan compared with companies’ existing methods. In satellite manufacturing, an improved NEH algorithm produces flexible, automatic simulation modelling with high accuracy in acceptable time. Variants of the algorithm now appear in supply chain management, health services, defense planning, automation, and computer chip design.
For anyone following the current wave of AI development and Machine Learning (ML), NEH-descended methods reach further, touching data processing and cloud computing, self-driving vehicle systems, and satellite communications, fields where sequencing and optimization problems look strikingly similar to the one Nawaz solved.
Why It Still Matters
Papers in the field routinely open by acknowledging the NEH algorithm, and researchers have yet to produce anything that displaces it as the benchmark for simple, fast, high-quality scheduling solutions. It is a reminder that sometimes the most enduring ideas start small, get published in a journal, and quality becomes the foundation everything else is built on.
“The NEH algorithm, published in 1983 by Nawaz, Enscore, and Ham, remains irreplaceable in industrial engineering because it brought simplicity and efficiency to complex production scheduling problems,” said Bruno Prata, an industrial engineering researcher at the Federal University of Ceará in Brazil. “Even as more refined variants have emerged, its clarity and robustness continue to serve as a fundamental benchmark in industrial practice.”
That gap is, in its own way, the more interesting story: not what Nawaz built, but how far an idea can travel while the place it started from never finds out.
References
- Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95. https://www.sciencedirect.com/science/article/abs/pii/0305048383900889
- “Secuenciación en taller de flujo con la regla NEH.” Universitat Politècnica de València. https://www.youtube.com/watch?v=TcBzEyCQBxw
- “The Seeds of the NEH Algorithm: An Overview Using Bibliometric Analysis” by Bruno de Athayde Prata, Marcelo Seido Nagano, Nádia Junqueira Martarelli Fróes, and Levi Ribeiro de Abreu, SN Operations Research Forum, 4, 98 (2023). DOI: 10.1007/s43069-023-00276-7
- Masrikhan & Kurniawati, D. A. (2021). Flow shop scheduling based on Palmer-NEH, Gupta-NEH, and Dannenbring-NEH algorithms to minimize the energy cost. SINERGI, 25(2), 111–118. https://doi.org/10.22441/sinergi.2021.2.001
- Li, G., & Zhang, L. (2024). Discrete-event simulation integrates an improved NEH algorithm for practical flowshop scheduling problems in the satellite industry. Applied Sciences, 14(21), 9755. https://doi.org/10.3390/app14219755
- Framinan, J. M., & Leisten, R. (2003). Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing. International Journal of Production Research. https://www.tandfonline.com/doi/abs/10.1080/00207540210161650
- Loete Heijdenrijk (2023), Developing a real-time job scheduling model for a packaging process with practical restrictions at Euroma, MSc. Thesis, Universiteit Twente.
If you want to submit your articles and/or research papers, please visit the Submissions page.
To stay updated with the latest jobs, CSS news, internships, scholarships, and current affairs articles, join our Community Forum!
The views and opinions expressed in this article/paper are the author’s own and do not necessarily reflect the editorial position of Paradigm Shift.
Noor ul Huda is a mechatronics engineer and science and technology writer specialising in engineering, robotics, and finance. Her work is published on Medium at medium.com/@hudamajid. She can be reached at noorulhudarasool@gmail.com.
