Minimizing Makespan in Job Shop Scheduling Problem with Parallel Machines

In this paper the problem of job shop scheduling with parallel machines in each stages is discussed. The objective is to minimize the maximum completion time (makespan).�This problem is a combination of two classic problems of job shop and parallel machines which in this case parallel machines has been used as kind of flexibility in the job shop problem. The review of literature has shown that this problem has not been discussed yet. After presenting the mathematical mode, heuristic algorithms are used for solving this NP-hard problem. Regarding this, five algorithms are presented and a lower bound is developed. Finally all these algorithms have been analyzed. According to results the proposed algorithm of H2 works better than the others when there are few jobs. As the number of jobs increases H1 is more efficient than H2 asymptotically. Also the efficiency of H3 algorithm is the worst among the rest.