Abstract: Job-shop scheduling problem model with alternative machines is described. Based on genetic algorithms, a scheduling approach is presented, which can be used to solve the problem. A new chromosome representation with two-dimensional matrix is designed, which can enlarge traditional coding mode based on operators in expression of the machines. A new operation is introduced to change the extra information of the operator during the evolution process. The effectiveness of the proposed algorithm is verified by computation results (digital experiments) with two different scheduling objectives.