A divide and conquer-based greedy search for two-machine no-wait job shop problems with makespan minimisation

This paper addresses a two-machine no-wait job shop problem with makespan minimisation. It is well known that this problem is strongly NP-hard. A divide-and-conquer approach (DC for short) is adopted to calculate the optimal timetable of a given sequence. It decomposes the given sequences into several independent parts and conquers them separately. A timetable enhancing method is introduced to further improve the timetable obtained by DC. It constructs a set of flow shop type jobs based on the result from DC and calculates the best timetable for these newly constructed jobs by the well-known Gilmore and Gomory method (GG for short). An efficient greedy search is proposed by integrating DC with GG to search for the best sequence. Experimental results show that the proposed algorithm can find the optimal solutions for 96% of the randomly generated test instances on average.