缓冲区间有限条件下的作业车间调度方法

Job Shop Scheduling Problem with Limited Output Buffer

针对缓冲区间有限条件下的作业车间调度问题,以最小化make-span为目标建立了非线性混合整数规划模型,提出了基于邻域搜索的两阶段算法对问题进行求解.算法的第一阶段为迅速找到可行解,第二阶段为基于非连通图,通过邻域搜索对得到的可行解进行优化.针对benchmark算例进行测试并与已有的算法进行对比,验证了算法的有效性.对比分析发现,如果工件的加工时间符合均匀分布,当缓冲区间容量与工件数量的比例达到20%,缓冲区间大小对调度结果的影响将会迅速变小.

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.