New Heuristic for Job Shop Scheduling Problem

Abstract

As the job shop scheduling problems are difficult to solve in combinatorial optimization, research has been devoted to developing efficient heuristics and applying meta-heuristics. Due to their complexity, most forms of the JSSP are formally classified as NP-hard problems. The major implication of this classification is that there is no known solution technique that is guaranteed to obtain an optimal schedule, other than searching through all possibilities. However, an exhaustive search is almost always impractical given the vast number of permutations for even relatively small JSSPs. Consequently, researchers have focused their efforts on developing heuristic techniques that aim to construct the best possible schedule in a limited amount of time. One such heuristic method, Lowest Operation Time, is proposed in the present paper to solve Job Shop Scheduling Problems. Here the attention is focused on the long wait FT10 bench mark problem suggesting a heuristic procedure to solve it in minimum number of iterations to arrive at the desired makespan also a new scheduling measure namely Average Flow Time is reported that helps in picking up the best heuristic.