Abstract: The job shop problem with limited output buffers(JS-LOB)was addressed with the objective of minimizing the process make-span. An integer nonlinear mathematical programming(INLP)model was proposed to describe this problem. Based on the model， a two-stage algorithm consisting of obtaining feasible solutions and a local search was proposed to solve the JS-LOB problem. The operator in local search was a neighborhood structure based on a disjunctive graph model. Computational results were presented for a set of benchmark tests， some of which were enlarged by different proportions between the capacity of the buffer and the number of jobs. The results show the effectiveness of the proposed algorithm through comparing with other exist algorithms and indicate when the processing time of the job conforms to a uniform distribution， and when the proportion between the capacity of the buffer and the number of jobs is larger than 20%， the influence of the buffer will become very small.

Key words: job shop scheduling, limited output buffer, disjunctive graph, uniform distribution