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

Job Shop Scheduling Problem with Limited Output Buffer

作　　者：曾程宽 刘士新[1] ZENG Cheng-kuan;LIU Shi-xin(School of Information Science&Engineering,Northeastern University,Shenyang 110819,China)

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819

出　　处：《东北大学学报（自然科学版）》2018年第12期1679-1684,共6页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(71702028;61573089);国家自然科学基金创新群体项目(71621061);中国博士后科学基金资助项目(2017M621154);国家重点研发计划项目(2017YFB0306401)

摘　　要：针对缓冲区间有限条件下的作业车间调度问题,以最小化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.

关 键 词：作业车间调度 缓冲区间有限 非连通图 均匀分布 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]