Abstract: Based on constraint satisfaction this paper proposes a new adaptive neural network, and an efficient heuristics hybrid algorithm for Job-shop scheduling. The neural network has the property of adapting its connection weights and biases of neural units while solving feasible solution. Heuristics are used to improve he property of neural network and to obtain local optimal solution from solved feasible solution by neural network with orders of operations determined and unchanged. Computer simulations have shown that the proposed hybrid algorithm is of high speed and excellent efficiency.