A lower bound for job shop scheduling problem with a parallel assembly stage by graph coloring approach

Scheduling is one of the most applicable problems in industry that is considerably studied by researchers in the recent years. It is necessary to extend the models that can be applied in real situations. To this end researchers have tried to consider assembly and processing stages simultaneously. In this research according to the importance of different production stages in industry, and also to consider problem in real situation, job shop scheduling problem by considering a parallel assembly stage is studied to minimize completion time for all products. At first, this problem is reduced to graph coloring. Because this problem and graph coloring problem are NP-hard, a hybrid Genetic-Particle swarm optimization algorithm for medium and large size problems used. So in this research a lower bound for this problem based on graph coloring problem is proposed to evaluate the efficiency and effectiveness of the proposed algorithm. Keywords: Scheduling, Job shop, Parallel Assembly, Graph Coloring