Scheduling of a job-shop problem with limited output buffers

ABSTRACT

This article addresses a job-shop problem with limited output buffers (JS-LOB) with the objective of minimizing the process makespan. An integer nonlinear mathematical programming model is proposed to describe this problem. Based on the model, a two-stage algorithm consisting of obtaining feasible solutions and a local search is proposed to solve the JS-LOB problem. The local search has two operators: the first is a neighbourhood structure based on a disjunctive graph model, and the second is similar to crossover in the genetic algorithm to avoid falling into local optima. Computational results are presented for a set of benchmark tests. The results show the effectiveness of the proposed algorithm and indicate whether the processing time of the job conforms to a uniform distribution. When the proportion between the capacity of the buffer and the number of jobs is larger than 20%, the influence of the buffer becomes very small.