Analysis of Algorithms for Calculating Job Shop Scheduling Problem's Makespan

JSSP(Job Shop Scheduling Problem) is a well-known NP-hard problem. In this paper the JSSP is divided into two parts: one for calculating the makespan, the other for finding a scheduling which has the minimum makespan. Up to now the papers published are all focused on how to find an algorithm for finding the schedule that has minimum makespan quickly. Seldom papers talk about a related topic, that is the algorithm for calculating the makespan.Several algorithms are shown and discussed for that purpose in detail.The experimental result shows that there is a big difference among the speed of these algorithms. The analysis also indicates that the difference realization of algorithms may cause different result, even the wrong result. From the experiment and analysis, it can be seen that the speed of parallel simulation clock advance algorithm is the fastest. It is very useful for some iterative algorithm such as genetic algorithm for finding the schedule that has minimum makespan.