Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)
Mechanical Engineering     
Hybrid heuristic algorithm for integrated scheduling in  flexible Job Shops
ZHOU Bing hai, ZHAO Meng
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
Download:   PDF(994KB) HTML
Export: BibTeX | EndNote (RIS)      

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.

Published: 01 June 2016
CLC:     
  TP 29  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

ZHOU Bing hai, ZHAO Meng. Hybrid heuristic algorithm for integrated scheduling in  flexible Job Shops. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(6): 1073-1079.

URL:

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


柔性Job Shops集成调度启发式算法

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

［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] DONG Kai, LAI Jun ying, QIAN Xiao qian, ZHAN Shu lin, RUAN Fang. Energy efficiency of residential buildings with horizontal external shading in hot summer and cold winter zone[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1431-1437.
[2] LI Jia qi, FAN Li wu, YU Zi tao. Boiling heat transfer characteristics during quench cooling on superhydrophilic surface[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1493-1498.
[3] CHIANG Yen ming, ZHANG Jian quan, MING Yan. Flood forecasting by ensemble neural networks[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1471-1478.
[4] ZHONG Wei, PENG Liang, ZHOU Yong gang, XU Jian, CONG Fei yun. Slagging diagnosis of boiler based on wavelet packet analysis and support vector machine[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1499-1506.
[5] XIA Yu feng, REN Li, YE Cai hong, WANG Li. Multi-objective optimization of locators layout of reinforced panel based on RSM[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1600-1607.
[6] LI Lin yu, WU Zhang hua, YU Guo yao, DAI Wei, LUO Er cang.
Experimental investigation on electroacoustic conversion characteristic of linear compressor
[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1529-1536.
[7] QU Wei wei, TANG Wei, BI Yun bo, LI Shao bo, LUO Shui jun. Pre-joining processes plan to avoid forced assemblies and improve efficiency[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1561-1569.
[8] HU Xiao dong, GU Lin yi, ZHANG Fan meng. High-speed on/off valves applied in digital displacement motor[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1551-1560.
[9] YANG Shu, LIU Guo ping, QI Chang, WANG Da zhi. Simulation and optimization for anti-shock performances of graded metal hollow sphere foam structure[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1593-1599.
[10] YANG Zhang, TONG Gen shu, ZHANG Lei. Effective Rigidity of two one-side stiffeners arranged symmetrically[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1446-1455.
[11] JIANG Xiang, TONG Gen shu, ZHANG Lei. Experiments on fire-resistance performance of fire-resistant steel-concrete composite beams[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1463-1470.
[12] SHAN Hua feng, XIA Tang dai, YU Feng, HU Jun hua,PAN Jin long. Buckling stability analysis on critical load of underpinning pile for excavation beneath existing building[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1425-1430.
[13] GU Tian lai, ZHANG Shuai, ZHENG Yao. Back pressure characteristics of jaws inlet with constant-area isolator[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(7): 1418-1424.
[14] CHENG Shi wei, LU Yu hua, CAI Hong gang. Mobile device based eye tracking technology[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(6): 1160-1166.
[15] HUANG Jia hui, FENG Dong qin. Method for vulnerability evaluation of Cyberphysical system based on generalized profit[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(6): 1119-1125.