From managing global supply chains to optimizing delivery routes, artificial intelligence is helping in industries to improve productivity and capacity of work. AI has widely influenced every facet of our daily lives to improve efficiency and augments human capabilities. Algorithms are playing a vital role in obtaining the optimized solution of problems. NEH (Nawaz, Enscore, Ham) algorithm is an efficient algorithm developed in the early ’80s that works by minimizing makespan for scheduling problems.
Today we are going to introduce with this brilliant engineer of Pakistan who developed the NEH algorithm in 1980 during his Master of Engineering at Pennsylvania State University, US, which is an essential part of almost all references or textbooks covering Scheduling topics. No graduate course on Scheduling is complete without a discussion on NEH. Furthermore, the paper covering the NEH algorithm is one of the most-cited research articles by a Pakistani, given the First or lead author was affiliated with a Pakistani institution (University college of Engineering, Taxila), as shown on the paper. Only a few research papers by Pakistani researchers as lead authors and affiliated Pakistani institutions have more than 1000 citations. A story was published by Pennsylvania State University, the US in October 2019, in their engineering news on Eng. Nawaz’s contribution to NEH algorithm advancement.
Mohammad Nawaz was born in Lahore completed his BSc from the University of engineering and technology, Lahore. After his Master from Pennsylvania State University, the US, he has been served in the University of Engineering and Technology, Taxila. Here are some excerpts of his conversation with our Editor-in-Chief Saadeqa Khan.
Let us know about your academics and who inspired you the most in such an offbeat career in early 1980?
In my school years, the teachers who inspired me were mathematics teachers. If to name one that influenced me the most was my year 9 & 10-grade mathematics teacher, Mr. Sheikh Abdul Qadir, whom we used to call Baba. He had his own notes to teach us and textbooks even he asked us not to buy books – He was a true inspiration due to his devotion to his profession and indeed was a rare example in the 1960s era.
Another teacher of mine, Professor Emory Enscore of Penn State University, was the Supervisor of my Master thesis. He was an excellent Professor and a gentleman who showed me the real essence of academic integrity and professionalism. I honestly give all credit for the publication of my paper to Prof Enscore.
Let us know an event that would have proved as a turning point in your life?
During 1978-80, I was a Graduate student at Pennsylvania State University, USA. As part of my M.Eng degree, in addition to other courses, I was supposed to do a six Credits Minor Research Project or Thesis. I chose ‘Scheduling’ as my Research field and Professor Emory Enscore Jr as my Supervisor and Professor Inyong Ham as Second Supervisor. I had only six months to complete the research work, write the report, and get it typed in the approved format. Two months passed by, and I had no clear direction.
One day, an idea sprang in my mind to solve the ‘problem’ that was completely different than what other researchers were working on in this field. I tried the approach on a few examples, and it worked. I shared it with Prof Enscore, and he provided me enough computing time to prove that my ‘heuristic’ was at least as useful as past researchers’ work. Since there were no PCs in the ’70s or early ’80s, and we had only one big IBM mainframe in Penn State, and I had to do all my work in the PSU Computer Centre). I did prove that my heuristic (self-programming approach) was best to be considered for future work. I completed my research work within three months and handed over a copy of my short thesis to Prof Enscore. He went through and made corrections in a week or so. I got my thesis typed and submitted for final approval. The whole process did not take more than 6 months. I got my MEng degree at the end of August 1980 and decided to go back to Pakistan.
Just two weeks before my departure to Pakistan, Prof Enscore asked me to write a paper summarizing my research. He thought my work was worthy of being considered for publication. I did whatever I could and gave a handwritten copy of the work to him before leaving for Pakistan.
Prof Enscore converted my work in a proper format and submitted to a research journal. The journal sent the paper to referees for comments; the referees asked for further analysis and evaluation of the proposed heuristic algorithm. I was in Taxila, Pakistan, and had no computing facility to do any statistical analysis. Prof Enscore assigned the job to another of his Master student, YB Park analyzed and got his own MEng degree. Late 1981, Prof Enscore submitted the paper with my algorithm, and its evaluation to Omega – The International Journal of Management Science for publication, Omega accepted the newspaper in July 1982 and published in January 1983.
Prof Enscore had an excellent academic of integrity when I finished my studies at Penn State University, I did not think of getting the paper published. From September 1980 to January 1983 – the paper publication date, there was not much communication between me and Prof Enscore – just a couple of letters. I’m talking about pre-email times; there were no fax machines; there were only a couple of phone lines in the Taxila campus, and because of the time difference between Taxila and Penn State, it was hard to make phone calls. Prof Enscore did all the work – putting the work in a proper format for publication, communicating with journals, asking another researcher to do further analysis, and much more. He could have put his name as the First Author, but he did not. He put my name – as the First Author, and University College of Engineering, Pakistan as my affiliation just because I was working in the College at the time.
I Salute to Emory Enscore and believe that such academic integrity is nearly impossible in Pakistan until and unless our teachers devote their life and all energies to their profession.
What is the NEH (Nawaz Encore Ham) algorithm? How can it be useful for improved quality solutions?
Before talking about the NEH algorithm, I would like to elaborate on a couple of simple terms for the lay-readers.
Sequencing
The sequencing problem is a method of defining an order in which tasks to be done. In other words, the sequencing problem involves the determination of the relative position of tasks amongst all others. An issue may include jobs in a manufacturing plant, aircrafts waiting for landing clearance, customer orders in a fast-food facility, programs to be executed in a computer, loads of linen to wash and iron in an industrial laundry, etc.
Let’s consider this: you have two jobs, there are two possible sequences. Similarly, if there were 3 jobs, the possible sequences would be six. And if you have 10 jobs to execute, mathematically you would have 3,628,800 (a factorial of 10) possible sequences. Now imagine, you have 50 jobs, how many possible sequences are there? Possibly 50 factorial.
If all jobs are exactly the same, it does not make any difference in which sequence you choose from. However, if each job is different, we need to determine which the best sequence is. In the case of 2 or 3 jobs, one can quickly check which the best out of 2 or 6 is. However, if we have 50 or 100 jobs, there is no way to check every possible sequence to find the best one.
Flow-shop
Flow-shop is a term used for a system where all tasks are to process on machine 1, namely processer 1, then to machine 2 (processor 2), and so on. A simple example is, consider an industrial laundry; where Loads of dirty linen from local hospitals, to be washed first in a washing machine (machine 1), then go to a dryer (machine 2), then to ironing press (machine 3). The sequence of loads remains on all machines.
If one keeps the same sequence of all works on every machine, the problem becomes a bit simpler; this problem is called Permutation Flow-Shop Problem (PFSP).
Scheduling
Scheduling is just a timetable indicating the start and finish of any job on any machine or conversely, the beginning of the first job on the first machine which will end up the last job on the last machine.
For researchers or practitioners, the question is which sequence is the best out of many possible ones. But before this, one must decide what criterion is to be used to judge if the selected sequence is the best. One criterion used for PFSP (easiest flow-shop) is the Minimization of Makespan – the time between the starting of the first job on the first machine and finishing the last job on the last machine.
Now back to your question, Johnson SM (1954) developed an algorithm to find the optimal solution for the PFSP for any number of jobs, but only for 2 machines (3 machines only as a special case). Theoretically, one can find the optimal sequence for any number of jobs and any number of machines, but for a larger number of jobs and machines, the time required to get optimal is prohibitive.
NEH (Nawaz, Enscore, Ham) is a heuristic algorithm to find a sequence of jobs to Minimize the Makespan for a PFSP for any number of jobs and any number of machines. The NEH algorithm gives a very quick and good solution. The algorithm uses a simple strategy to evaluate only a small number of sequences to get a better solution. For example, if we have 10 jobs, to process on any number of machines, the algorithm evaluates only 55 sequences. The algorithm does not guarantee optimal but gives an excellent sequence most of the time. Many researchers have dissected the working of this simple algorithm, analyzed its results, and found it be one of the best. The algorithm is straightforward; it needs only a few lines of coding.
NEH and your name are well-known in the decision Sciences or Scheduling field, but I could not find an academic article/ research or a simple blog about your work in Pakistani publications. How can we popularize scientific research and breakthrough news in our media?
I would like to make it clear that the NEH algorithm is ‘older enough; however, my paper’s citations and NEH’s applications are increasing with time. One can check Google Scholar and Scopus for its citations.
In general, a lot of research is being done in the scheduling field in many institutions around the world; for the last 10 years, most papers are from China. Interestingly, many researchers from Iran are publishing excellent articles in reputable journals in the field too. One can see NEH’s applications in those papers.
I have seen a few outstanding papers in international journals by Pakistani researchers referring to my algorithm. Almost all these papers by Pakistani researchers are in collaboration with Chinese academic institutions.
How to popularize scientific research and breakthrough news in media? People like to read stories or articles or watch a program only of their interest. For the average person, the new medicine is a news, and average (popular) media gives coverage of this. Even in this case, the benefits of modern medicine would be given in detail, but there could be no mention of a scientist(s) or researcher(s) who developed the drug.
On the other hand, if someone develops a new variety of wheat, it would not make a news item in the popular media at all. Then what can we do? Here are a few suggestions:
- Pakistan needs more science magazines like your Scientia Pakistan, Spectra, and Global science along with skilled scientist journalists who can write articles acceptable to news outlets such as DAWN or Tribune. Not everybody would read those articles, but a specific intellectual circle is really interested in topics.
- Pakistani scientists, engineers, mathematicians, researchers, and most importantly, academics should visit institutions other than their own to present their research works. HEC, NSF, and similar organizations should support this type of program.
- Students of M.Sc, M Phil and Ph.D., should be asked to visit Degree and Intermediate Colleges to show Pakistani researchers’ works.
- College Principals and School Heads should be ‘trained’ to popularize science in their institutions.
- Trainees in Teaching Training College should be coached on how to get Pakistani scientists or researchers’ success stories and then pass on to students and media.
How much further study and improvements have been done in the NEH algorithm since 1983 when you developed it?
The NEH was devised to minimize makespan; however, its concept has been used to solve other related PFSP problems like minimization of average flow- time; this is the amount of time machine takes to process all the steps include wait or a rework. A number of researchers have also developed many variants of NEH to tackle different problems. Like, in 1990, Eric Taillard, did not change my algorithm but suggested improvement to cut down its computing time. Some researchers call this the Taillard’s accelerated NEH.
You developed the NEH algorithm as a part of your Master of Engineering program at Pennsylvania State University, US, in 1980. Let us know about its importance in academics?
The NEH algorithm is in almost all references or textbooks covering Scheduling topics. No graduate course on Scheduling is complete without a discussion on NEH.
The PSU, the US, has recently published a story on the NEH algorithm in its yearly magazine as a highly cited publication in Omega. How do you feel about such a significant achievement?
The paper covering the NEH algorithm is one of the most-cited research articles by a Pakistani, given the First or lead author was affiliated with a Pakistani institution, as shown in the paper. Only a few research papers by Pakistani researchers as lead authors and affiliated Pakistani institutions have more than 1000 citations.
How do I feel myself? Well, I usually see two or three citations every week, and sometimes a new article with NEH in the title, I feel content and pleasure that my contribution to the scheduling field is worthwhile. But I equally ponder why? I’m not a hardworking person, I’m not a good researcher/writer; the answer comes – Sometimes Allah gives you than what you deserve.
Below is the story published in PSU Engineering News:
Let us know about some NEH algorithm applications in non-manufacturing disciplines?
An important example of NEH algorithm applications in non-manufacturing disciplines is as under.
Search for missing Tourist
In recent years, there have been overwhelming incidents of missing tourists around the world. The use of unmanned aerial vehicles (UAVs) has significantly improved the performance of search and rescue operations. However, planning the search paths of UAVs can be a highly complex optimization problem, and one of the most challenging tasks in the problem formulation is the estimation of target location probability distribution over time. This method presents a UAV, s solution to search for missing tourists, and also proposed estimation of tourist location probabilities which change with topographic features, weather conditions, and time.
A couple of other useful applications of the NEH algorithm is Primitive matching in World Wide Web searching and energy-efficient real-time computing.
Google has recently announced breakthrough research on Quantum computing, which enables new generation computers to work on the fastest speed. What do you think Super AI will be beneficial or harmful for humankind?
AI is beneficial for humankind, but ONLY if it is used for good causes. The AI is a technology, its benefits or harms depend on its users, just like nuclear technology that can be applied to cure deceased, or to generate electricity for lighting homes, and the same technology can be used to kill thousands of people in minutes.
Also, read Cancer; From hope to possible care
