考虑有限缓存区的Job Shop加工与搬运集成调度

doi:10.12005/orms.2020.0303

运筹与管理 ›› 2020, Vol. 29 ›› Issue (11): 213-222.DOI: 10.12005/orms.2020.0303

考虑有限缓存区的Job Shop加工与搬运集成调度

张维存, 左天帅, 张博涵

河北工业大学经济管理学院,天津 300401

收稿日期:2019-05-30 出版日期:2020-11-25 发布日期:2023-07-12
作者简介:张维存(1975-),男,河北乐亭人,副教授,博士,研究领域:车间调度、供应链管理、智能优化算法等;左天帅(1993-),男,天津人,硕士研究生,研究领域:车间调度和智能优化算法;张博涵(1993-),男,河北清河人,硕士研究生,研究领域:车间调度和智能优化算法。
基金资助:
国家社科基金资助项目(17BGL087); 河北省高等学校自然科学青年基金项目(2011125)

JobShop Processing and Handling Integrated Scheduling with Limited Buffers.

ZHANG Wei-cun, ZU0Tian-shuai, ZHANG Bo-han

School of Economics and Management, Hebei Univercity of Technology, Tianjin 300401,China

Received:2019-05-30 Online:2020-11-25 Published:2023-07-12

摘要/Abstract

摘要： 在Job Shop环境下,以最小化最大完工时间为目标,考虑了搬运设备与有限缓存区对加工过程的影响,建立了带有限缓存区的Job Shop加工与搬运集成调度模型,并设计了改进的人工蜂群优化算法求解此问题。首先,在算法中引入了引领蜂和跟随蜂角色互换的机制,可更好的兼顾全局广泛寻优和局部精确寻优。其次,基于问题的特殊性,工序既是加工任务也是搬运任务,所以在编码方式上采取基于工序编码,便于算法运行过程中解码计算。然后,在解码过程中,为提高算法运行效率,设计了如何确定解码加工任务和搬运任务的启发式信息。最后,通过标准测例实验比较,给出了本文G-ABC算法种群规模的建议取值范围,并证明了G-ABC算法的有效性,启发式信息的有效性以及缓存区容量设置对调度结果的影响。

关键词: Job Shop, 有限缓存区, 搬运设备, 集成调度, 蜂群算法

Abstract: In the condition of Job Shop, aiming at minimizing the maximum completion time, considering the influence of handling equipment and the limitation of buffer on the processing process, an integrated scheduling model of Job Shop processing and handling with limited buffers is established, and an improved artificial bee colony optimization algorithm is designed to solve the problem. Firstly, the mechanism exchange between the role of leader bee and follower bee is introduced in the algorithm, which can give better consideration to global wide optimization and local precise optimization. Secondly, based on the particularity of the problem, the process is not only a processing task but also a handling task, so the coding method is based on the process coding, which is convenient for decoding and calculation in the process of algorithm operation. Then, in the decoding process, in order to improve the efficiency of the algorithm, the heuristic information is designed to determine decoding processing tasks and handling tasks. Finally, the recommended range of population size of G-ABC algorithm is given by comparing the standard test cases. The paper proves the validity of G-A BC algorithm, the effectiveness of heuristic information and the influence of buffer capacity setting on scheduling results.

Key words: Job Shop, limited buffers, handling equipment, integrated scheduling, bee colony al gorithm

中图分类号:

TP305
TH166

张维存, 左天帅, 张博涵. 考虑有限缓存区的Job Shop加工与搬运集成调度[J]. 运筹与管理, 2020, 29(11): 213-222.

ZHANG Wei-cun, ZU0Tian-shuai, ZHANG Bo-han. JobShop Processing and Handling Integrated Scheduling with Limited Buffers.[J]. Operations Research and Management Science, 2020, 29(11): 213-222.

参考文献

[1] Egbelu P J, Tanchoco J M A. Characterization of auto-matic guided vehicle dispatching rules[J]. International Journal of Production Research, 1984, 22(3):359-374.
[2] Hurink J, Knust S.A tabu search algorithm for schedu-ling a single robot in a job-shop environment[J].Discrete A pplied Mathematics, 2002, 119(1):181-203.
[3] Hurink J, Knust S.Tabu search algorithms for job-shop problems with a single transport robot [J]. European Journal of Operational Research, 2005, 162(1):99-111.
[4] 何之洲,杨煜俊,陈新度.带搬运机器人的job-shop问题的并行禁忌搜索算法[J].工业工程,2013,16(4):122-125.
[5] Deroussi L, Gourgand M, Tchernev N.A simple meta-heuristic approach to the simultaneous scheduling of ma-chines and automated guided vehicles [J]. International Journal of Production Research, 2008, 46(8):2143-2164.
[6] Nouri H E, Driss O B, Ghedira, Khaled.Simultaneous scheduling of machines and transport robots in flexible job shop environment using hybrid metaheuristics based on clustered holonic mutliagent model[J]. Computers & Industrial Engineering, 2016, 102: 488-501.
[7] 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.
[8] Zheng Y, Xiao Y, Seo Y.A tabu search algorithm for simultaneous machine/ AGV scheduling problem[J].International Journal of Production Research, 2014, 52(19): 5748-5763.
[9] Umar U A,Ariffin M K A, Ismail N, et al. Hybridmul-tiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle(AGV)in flexible manufacturing systems, 2015, 81: 2123-2141.
[10] 孔继利,苑春荟,杨福兴,贾国柱.带搬运时间的批量生产制造系统生产作业计划方法[J].系统工程理论与实践,2015,35(11):2821-2831.
[11] Bekkar A, Guemri 0, Bekrar A, et al. An iterative greedy insertion technique for flexible job shop schedu-ling problem[J]. IF AC-PapersOnLine, 2016, 49(12):1956-1961.
[12] Karimi S, Ardalan Z, Naderi B, et al.Scheduling flexi-ble job-shops with transportation times: mathematical models and a hybrid imperialist competitive algorithm[J]. Applied Mathematical Modelling, 2017, 7(41):667-682.
[13] Nouri H E, Driss O B, Ghedira K.Optimizing robot movements in flexible job shop env ironment by metaheu-ristics based on clustered holonic multiagent model[C]. 13th International Conference of Modeling Decisions for Artificial Intelligence, 2016. 275-288.
[14] 周炳海,赵猛.柔性Job Shops集成调度启发式算法[J].浙江大学学报(工学版), 2016, (06):1073-1079,1125.
[15] Thi Rer M, Godinho Filho M, et al.Coping with finite storage space in job shops through order release control: an assessment by simulation [J]. International Journal of Computer Integrated M anufacturing, 2013, 26(9):830-838.
[16] Escamilla J, Rodriguez-Molins M, Salido M A, et al.Robust solutions to job-shop scheduling problems with operators[C]. EEE International Conference on TOOIS with Artificial Intelligence. EEE, 2012. 299-306.
[17] Zhang Q.A hylisd metahessristic algorithm for tlexible job-shop scheduling problems with tsanspor tation con-straints[C] Proceedings of the 14 th International Confe-wence on Genetic and Evalutionasy Computation 2012:441-448.
[18] 王政球. 装配单元缓冲区容量仿真优化[D].广东工业大学,2016.
[19] 曹振新, 鄂世举,焦卫东,等.基于马尔科夫链的混流装配线缓冲区配置优化研究[J].新技术新工艺, 2015(6):29-33.
[20] 吕洁,郭婷芳,韩文民.虚拟制造单元瓶颈缓冲区容量优化[J].组合机床与自动化加工技术,2016(12):121-124.
[21] 陈冠中,陈庆新,毛宁,等.智能制造系统AGV小车及缓冲区容量仿真优化[J].工业工程,2016, 19(3):77-84.
[22] 郭丽. 自适应差分进化算法解决多目标有限缓冲车间调度问题研究[D].郑州大学,2016.
[23] 任晓莉. LSO改进CGA解决多目标JobShop问题[J].计算机应用与软件,2015,32(3):60-64.
[24] Umit Bilge, Ulusoy G.Time w indow approach to simul-taneous scheduling of machines and material handling system in an FMS[J]. Operations Research, 1995, 43(6): 1058-1070.
[25] Erol R, Sahin C, Baykasoglu A, et al.A multi-agent based approach to dynamic scheduling of machines and automated guided vehicles in manufacturing systems [J]. Applied Soft Computing Jourmal, 2012, 12(6):1720-1732.
[26] 龙传泽,杨煜俊.基于遗传算法的柔性机器人制造单元调度问题研究[J].组合机床与自动化加工技术, 2015(11):141-144, 148.

考虑有限缓存区的Job Shop加工与搬运集成调度

JobShop Processing and Handling Integrated Scheduling with Limited Buffers.

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	陈伟, 张玉林. “仓店一体化”模式下订单拣选与配送集成调度优化[J]. 运筹与管理, 2021, 30(7): 16-22.
[2]	郑红星, 尹昊, 曹红雷, 石岳. 考虑潮汐影响的离散型泊位和岸桥集成调度[J]. 运筹与管理, 2017, 26(6): 167-175.
[3]	柳寅, 马良, 黄钰. 模糊人工蜂群算法的多选择多维背包问题求解[J]. 运筹与管理, 2013, 22(5): 98-103.