Every company engaged in the manufacturing industry must implement a productivity improvement program. In avoiding the occurrence of queues in the manufacturing process, an overall solution is needed. One that is often used in scheduling systems is the flow shop pattern.

FCFS are the most widely used methods, this method schedules work without paying attention to makespan, so that with this method there are often delays and inefficient production costs. According to Utami (2020) the CDS method produces a better solution than the FCFS but Jin et. Al (2007) state that the NEH method produces a more optimal solution than the CDS method, but the NEH method provides a longer computational time. The purpose of this study was to develop a new method for solving flow shop scheduling problems based on the concept of the CDS and NEH methods namely NEHLPD, NEHLPD1, NEHLPD2 and then tested them on random cases.

Based on the results of running on 30 cases, it was found that: NEHLPD produces more efficient makespan than the CDS method and the NEH method where the average efficiency level is 3.56% and 0.28%, respectively; NEHLPD1 produces 9.67% faster computational time than the CDS method and 74.72% than the NEH method; NEHLPD2 produces a processing time of 12.41% faster than the NEH method and produces an average makespan solution of 1.84% better than the CDS method and only 1.49% worse than the makespan of NEH method.