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

doi:10.12068/j.issn.1005-3026.2018.12.002

东北大学学报:自然科学版 ›› 2018, Vol. 39 ›› Issue (12): 1679-1684.DOI: 10.12068/j.issn.1005-3026.2018.12.002

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

曾程宽，刘士新

(东北大学信息科学与工程学院，辽宁沈阳110819)

收稿日期:2017-09-20 修回日期:2017-09-20 出版日期:2018-12-15 发布日期:2018-12-19
通讯作者: 曾程宽
作者简介:曾程宽(1988-)，男，辽宁沈阳人，东北大学讲师，博士；刘士新(1968-)，男，辽宁调兵山人，东北大学教授，博士生导师.冯明杰(1971-)，男，河南禹州人，东北大学副教授; 王恩刚(1962-)，男，辽宁沈阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(51171041).国家自然科学基金资助项目(71702028，61573089)；中国博士后科学基金资助项目(2017M621154)；国家重点研发计划项目(2017YFB0306401)；国家自然科学基金创新群体项目(71621061).

Job Shop Scheduling Problem with Limited Output Buffer

ZENG Cheng-kuan¹， LIU Shi-xin¹

School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.

Received:2017-09-20 Revised:2017-09-20 Online:2018-12-15 Published:2018-12-19
Contact: ZENG Cheng-kuan
About author:-
Supported by:
-

摘要/Abstract

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

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

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

中图分类号:

TP301.6

曾程宽，刘士新. 缓冲区间有限条件下的作业车间调度方法[J]. 东北大学学报:自然科学版, 2018, 39(12): 1679-1684.

ZENG Cheng-kuan， LIU Shi-xin. Job Shop Scheduling Problem with Limited Output Buffer[J]. Journal of Northeastern University Natural Science, 2018, 39(12): 1679-1684.

参考文献

[1]Brucker P，Heitmann S，Hurink J，et al.Job-shop scheduling with limited capacity buffers［J］.OR Spectrum，2006，28(2):151-176.
[2]Lacomme P，Larabi M，Tchernev N.Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles［J］.International Journal of Production Economics，2013，143(1):24-34.
[3]Hsieh Y C，You P S，Liou C D.A note of using effective immune based approach for the flow shop scheduling with buffers［J］.Applied Mathematics and Computation，2009，215(5):1984-1989.
[4]Pan Q K，Wang L，Gao L.A chaotic harmony search algorithm for the flow shop scheduling problem with limited buffers［J］.Applied Soft Computing，2011，11(8):5270-5280.
[5]Pan Q K，Wang L，Gao L，et al.An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers［J］.Information Sciences，2011，181(3):668-685.
[6]Wang L，Zhang L，Zheng D Z.An effective hybrid genetic algorithm for flow shop scheduling with limited buffers［J］.Computers & Operations Research，2006，33(10):2960-2971.
[7]Xie Z P，Zhang C Y，Shao X Y，et al.Flow shop scheduling with limited buffers based on memetic algorithm ［J］.Computer Integrated Manufacturing Systems，2015，21(5):1253-1261.
[8]Pan Q K，Tasgetiren M F，Suganthan P N，et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem ［J］.Information Sciences，2011，181(12):2455-2468.
[9]Zhang C，Shi Z S，Huang Z W，et al.Flow shop scheduling with a batch processor and limited buffer［J］.International Journal of Production Research，2017，55(11):3217-3233.
[10]Nawaz M，Enscore E E J，Ham I.A heuristic algorithm for the m-machine，n-job flow shop sequencing problem［J］.Omega-International Journal of Management Science，1983，11(1):91-95.
[11]Zeng C K，Tang J F，Yan C J.Job-shop cell-scheduling problem with inter-cell moves and automated guided vehicles［J］.Journal of Intelligent Manufacturing，2015，26(5):845-859.
[12]Lawrence S.Supplement to resource constrained project scheduling:an experimental investigation of heuristic scheduling techniques［R］.Pittsburgh:Carnegie Mellon University，1984.
[13]Grflin H，Klinkert A.A new neighborhood and tabu search for the blocking job shop［J］.Discrete Applied Mathematics，2009，157(17):3643-3655.

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

Job Shop Scheduling Problem with Limited Output Buffer

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	王天宝，吴成东，王玉龙，张云洲. 基于多包传输的网络控制系统控制器设计[J]. 东北大学学报(自然科学版), 2013, 34(2): 157-161.
[2]	王天宝;吴成东;张云洲;纪鹏;. 具有丢包和非均匀分布时延的网络控制器设计[J]. 东北大学学报(自然科学版), 2012, 33(8): 1084-1087+1092.
[3]	马佳;高立群;石刚;李丹;. 求解柔性作业车间调度问题的免疫遗传算法[J]. 东北大学学报(自然科学版), 2008, 29(7): 936-939.
[4]	刘晓霞;谢里阳;陶泽;郝长中;. 基于生产费用的柔性作业车间调度优化[J]. 东北大学学报(自然科学版), 2008, 29(4): 561-564.
[5]	黄宝宗;姜泽亚. 加筋板的局部屈曲[J]. 东北大学学报:自然科学版, 1984, 5(3): 55-63+129.
[6]	梁志德;徐家桢;王福. TA7合金薄板冷轧织构的三维取向分析[J]. 东北大学学报:自然科学版, 1981, 2(2): 7-15.