Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
机械工程     
柔性Job Shops集成调度启发式算法
周炳海, 赵猛
同济大学 机械与能源工程学院,上海 201804
Hybrid heuristic algorithm for integrated scheduling in  flexible Job Shops
ZHOU Bing hai, ZHAO Meng
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
 全文: PDF(994 KB)   HTML
摘要：

为有效解决柔性作业车间（Job Shops）的加工与搬运集成调度问题,以最小化最大完工时间(Makespan)为调度目标,建立非线性规划模型,提出基于贪婪启发式策略的变邻域搜索算法(GRSRVNS).根据准时(JIT)生产和均衡生产思想构建贪婪启发式策略快速求初始解.利用析取图表示可行解并根据析取图调度的性质定理构建有效的搜索邻域,进而利用随机变邻域搜索算法对初始解进行优化.对提出的算法进行仿真实验分析,结果表明：该算法求解时间短、调度方法有竞争性.
Abstract:

 The nonlinear programming model was developed with an objective of minimizing system Makespan to solve the integrated scheduling problem of processing and handling in flexible job shops effectively. A greedy heuristic strategy based variable neighborhood search algorithm (GRSRVNS) was put forward. The greedy heuristic strategy was designed with the combination of the just in time (JIT) and balanced production ideas, in order to get initial solution rapidly. An effective neighbor was constructed based on the disjunctive graph representations of the feasible solutions and properties and theorems of the disjunctive graph scheduling. The neighbor was used in the random variable neighborhood search algorithm. Finally, the experiments were designed for the proposed algorithm. Results indicate that the computing time of the proposed algorithm is short and the scheduling method is promising.
出版日期: 2016-06-01
:     
基金资助:

国家自然科学基金资助项目（71471135，61273035）|国家“863”高技术研究发展计划资助项目（2009AA043000）.
作者简介: 周炳海(1965—), 男, 教授, 博导，从事离散制造系统维护、调度、建模与仿真研究.ORCID: 0000000265999033. E-mail: bhzhou@tongji.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

周炳海, 赵猛. 柔性Job Shops集成调度启发式算法[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008973X.2016.06.009.

ZHOU Bing hai, ZHAO Meng. Hybrid heuristic algorithm for integrated scheduling in  flexible Job Shops. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008973X.2016.06.009.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008973X.2016.06.009    或    http://www.zjujournals.com/eng/CN/Y2016/V50/I6/1073

［1］ 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.
［2］ BRUCKER P, BURKE E K, GROENEMEYER S. A mixed integer programming model for the cyclic jobshop problem with transportation ［J］. Discrete Applied Mathematics, 2012, 160(13): 1924-1935.
［3］ LEI D, GUO X. Scheduling job shop with lot streaming and transportation through a modified artificial bee colony ［J］. International Journal of Production Research, 2013, 51(16): 4930-4941.
［4］ CHAUDHRY I A, MAHMOOD S, SHAMI M. Simultaneous scheduling of machines and automated guided vehicles in flexible manufacturing systems using genetic algorithms ［J］. Journal of Central South University of Technology, 2011, 18(5): 1473-1486.
［5］ LACOMME P, LARABI M, TCHERNEV N. A disjunctive graph for the jobshop with several robot ［C］ ∥MISTA Conference. Paris: MISTA, 2007: 285-292.
［6］ 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.
［7］ DEROUSSI L, GOURGAND M, TCHERNEV N. A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles ［J］. International Journal of Production Research, 2008, 46(8): 2143-2164.
［8］ 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.
［9］ ZHANG Q, MANIER H, MANIER M A. A modified shifting bottleneck heuristic and disjunctive graph for job shop scheduling problems with transportation constraints ［J］. International Journal of Production Research, 2014, 52(4): 985-1002.
［10］ ZHANG Q, MANIER H, MANIER M A. A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times ［J］. Computers and Operations Research, 2012, 39(7): 1713-1723.
［11］ LIU Z, MA S, SHI Y, et al. Solving multiobjective flexible Job Shop scheduling with transportation constraints using a micro artificial bee colony algorithm ［C］ ∥ 2013 IEEE 17th International Conference on Computer Supported Cooperative Work in Design (CSCWD). Whistler： IEEE, 2013: 427-432.
［12］ DRIESSEL R, MNCH L. Variable neighborhood search approaches for scheduling jobs on parallel machines with sequencedependent setup times, precedence constraints, and ready times ［J］. Computers and Industrial Engineering, 2011, 61(2): 336-345.
［13］ MLADENOVI N, TODOSIJEVI R, UROEVI D. Two level General variable neighborhood search for Attractive traveling salesman problem ［J］. Computers and Operations Research, 2014, 52(1): 341-348.
［14］ MLADENOVI N, TODOSIJEVI R, UROEVI D. Less is more: Basic variable neighborhood search for minimum differential dispersion problem ［J］. Information Sciences, 2016, 326: 160-171.
［15］ 严蔚敏, 吴伟民. 数据结构: C 语言版 ［M］.北京：清华大学出版社有限公司,2002.
［16］ BILGE , ULUSOY G. A time window approach to simultaneous scheduling of machines and material handling system in an FMS ［J］. Operations Research, 1995, 43(6): 1058-1070.
[1] 董凯, 赖俊英, 钱晓倩, 詹树林, 阮方. 夏热冬冷地区居住建筑水平式外遮阳节能效果[J]. 浙江大学学报(工学版), 2016, 50(8): 1431-1437.
[2] 李佳琦, 范利武, 俞自涛. 超亲水表面在淬火冷却过程中的沸腾传热特性[J]. 浙江大学学报(工学版), 2016, 50(8): 1493-1498.
[3] 江衍铭, 张建全, 明焱. 集合神经网络的洪水预报[J]. 浙江大学学报(工学版), 2016, 50(8): 1471-1478.
[4] 钟崴, 彭梁, 周永刚, 徐剑, 从飞云. 基于小波包分析和支持向量机的锅炉结渣诊断[J]. 浙江大学学报(工学版), 2016, 50(8): 1499-1506.
[5] 夏玉峰, 任莉, 叶彩红, 王力. 基于RSM的立柱加强板定位布局多目标优化[J]. 浙江大学学报(工学版), 2016, 50(8): 1600-1607.
[6] 李林玉, 吴张华, 余国瑶, 戴巍, 罗二仓. 直线压缩机电声转换特性的实验[J]. 浙江大学学报(工学版), 2016, 50(8): 1529-1536.
[7] 杨章, 童根树, 张磊. 对称布置2根单侧加劲肋的有效刚度[J]. 浙江大学学报(工学版), 2016, 50(8): 1446-1455.
[8] 蒋翔, 童根树, 张磊. 耐火钢-混凝土组合梁抗火性能试验[J]. 浙江大学学报(工学版), 2016, 50(8): 1463-1470.
[9] 曲巍崴, 唐伟, 毕运波, 李少波, 罗水均. 避免强迫装配和提升效率的预连接工艺规划[J]. 浙江大学学报(工学版), 2016, 50(8): 1561-1569.
[10] 胡小东, 顾临怡, 张范蒙. 应用于数字变量马达的高速开关阀[J]. 浙江大学学报(工学版), 2016, 50(8): 1551-1560.
[11] 杨姝, 刘国平, 亓昌, 王大志. 金属空心球梯度泡沫结构抗冲击特性仿真与优化[J]. 浙江大学学报(工学版), 2016, 50(8): 1593-1599.
[12] 单华峰, 夏唐代, 俞峰, 胡军华, 潘金龙. 地下增层开挖托换桩的屈曲稳定临界荷载分析[J]. 浙江大学学报(工学版), 2016, 50(8): 1425-1430.
[13] 辜天来,张帅,郑耀. 咽式进气道/等直隔离段的反压特性[J]. 浙江大学学报(工学版), 2016, 50(7): 1418-1424.
[14] 程时伟, 陆煜华, 蔡红刚. 移动设备眼动跟踪技术[J]. 浙江大学学报(工学版), 2016, 50(6): 1160-1166.
[15] 郑成志, 高金良, 何文杰. 基于FastICA算法的物理漏损流量分析模型[J]. 浙江大学学报(工学版), 2016, 50(6): 1031-1039.