The job shop scheduling problem has been studied for decades and known as an NP-hard problem for which no polynomial time algorithm has been found. However, most research results of job. shop scheduling problems focus on single objective problems and a big gap between scheduling theory and practice'still exists. A bi-objective job shop scheduling with alternative machines was researched by combining advantages of Genetic Algorithm (GA) With Simulated Annealing algorithm (SA) to address the reduction of make-span with the critical jobs' tardiness in this paper. The combination of GA and SA is using GA excellent global search ability and SA efficient to avoid getting into part minimum, which has higher degree of convergence precision. The critical jobs rnust be scheduled by using the backward algorithm, which ensures that the necessary resources are allocated to the most important jobs, and the remaining jobs with a forward algorithm which tends to allocate resources where the previous scheduling did not use them. Bi-direction scheduling meets both users' requirements and production efficiency, which possesses a strong practical application value. The results of the examples show that the procedure is available and efficient.
