[1]蔡良伟,李霞.基于混合蛙跳算法的作业车间调度优化[J].深圳大学学报理工版,2010,27(4):391-395.
　CAI Liang-wei and LI Xia.Optimization of job shop scheduling based on shuffled frog leaping algorithm[J].Journal of Shenzhen University Science and Engineering,2010,27(4):391-395.
点击复制

基于混合蛙跳算法的作业车间调度优化()
分享到：

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第27卷
期数:
2010年4期
页码:
391-395
栏目:
光电与信息工程
出版日期:
2010-10-31

文章信息/Info

Title:
Optimization of job shop scheduling based on shuffled frog leaping algorithm
文章编号:
1000-2618(2010)04-0391-05
作者:
蔡良伟; 李霞
深圳大学信息工程学院，深圳 518060
Author(s):
CAI Liang-wei and LI Xia
College of Information Engineering, Shenzhen University, Shenzhen 518060, P．R．China
关键词:
人工智能; 混合蛙跳算法; 作业车间调度; 智能计算; NP-hand组合优化
Keywords:
artificial intelligence; shuffled frog-leaping algorithm; job shop scheduling; intelligence computing; NP-hand optimization
分类号:
TP 181；TP 183
文献标志码:
A
摘要:
针对作业车间调度问题，提出改进的混合蛙跳算法．采用基于工件操作的蛙体结构，定义青蛙的相似性和距离，构造相应的青蛙移位策略，有效克服工件机器顺序的约束限制，保证青蛙新位置的可行性．通过经典算例仿真计算结果表明，该算法能有效求解较大规模的作业车间调度问题．
Abstract:
An improved shuffled frog-leaping algorithm is proposed for job shop scheduling problem．In this algorithm，the structure of frog is dependent on job operations．The similarity and distance between frogs are defined．A new displacement strategy is constructed，so that the constraint of machine sequence is overcome and the feasibility of frog’s new position is assured．Simulation results on benchmark problems show that this algorithm can effectively solve large job shop scheduling problems．

参考文献/References:

［1］Muth J F，Thompson G L．工业调度［M］．上鞍河（美国）：Prentice-Hall出版社，1963．(英文版)
［2］Liu T K，Tsai J T，Chou J H．作业车间调度问题的改进遗传算法［J］．先进制造技术，2006，27(9/10)：1021-1029．(英文版)
［3］杨晓梅，曾建潮．采用多个体交叉的遗传算法求解作业车间问题［J］．计算机集成制造系统，2004，10(9)：1114-1119．
［4］Wang T Y ， Wu K B．求解作业车间调度问题最小总延迟的改进模拟退火算法［J］．系统科学，2000，31(4)：537-542．(英文版)
［5］Suresh R K ，Mohanasundaram K M．多目标作业车间调度Pareto 模拟退火算法［J］．先进制造技术.，2006，29(1/2)：184-196．(英文版)
［6］Zhang J，Hu X M，Tan X，等．作业车间调度问题的蚁群优化技术实现［J］．仪器测量和控制，2006，28(1)：93-108．(英文版)
［7］LI Yan-jun，WU Tie-jun．混合生产调度的混合蚁群算法［J］．自动化学报，2003，29(1)：95-101．
［8］夏蔚军，吴智铭，张伟，等．微粒群优化在job-shop 调度中的应用［J］．上海交通大学学报，2005，39(3)：381-385．
［9］Tasgetiren M F，Sevkli M，Liang Y C，等．作业车间调度问题粒子群优化和差分进化［J］．运筹研究，2006，3(2)：120-135．(英文版)
［10］Eusuff M M，Lansey K E．求解水分布网络设计优化的混合蛙跳算法［J］．水资源计划和管理，2003，129(3)：210-225．(英文版)
［11］Eusuff M，Lansey K，Pasha F．混合蛙跳算法：离散优化的一种后启发式算法［J］．工程优化，2006，38(2)：129-154．(英文版)
［12］Liong Shie-yui，Atiquzzaman Md．利用混合进化进行水分布网络最优设计［J］，工程师杂志，2004，44(1)：93-107．(英文版)
［13］Hatem Elbehairy，Emad Elbeltagi，Tarek Hegazy，等．桥墩优化维修的两种进化算法比较［J］．计算机辅助民用与基础工程，2006(21)：561-572．(英文版)
［14］Elbeltagi E，Hegazy T，Grierson D．用于项目管理的一种改进混合蛙跳算法［J］．结构与基础工程，2007，3(1)：53-60．(英文版)
［15］Alireza Rahimi-Vahed，Ali Hossein Mirzaei ．用混合蛙跳算法求解双判据流水车间调度问题［J］．软计算，2007，12(5)：435-452．(英文版)
［16］骆剑平，李霞．求解TSP的改进混合蛙跳算法［J］．深圳大学学报理工版，2010，27(2)：173-179.


［1］Muth J F，Thompson G L．Industrial scheduling［M］．Upper Saddle River(USA)：Prentice-Hall，1963．
［2］Liu T K，Tsai J T，Chou J H．Improved genetic algorithm for the job-shop scheduling problem［J］．The International Journal of Advanced Manufacturing Technology，2006，27(9/10)：1021-1029．
［3］YANGXiao-mei，ZENGJian-zhao．Multi-individual-crossover genetic algorithm for job shop scheduling problem［J］．Computer Integrated Manufacturing Systems，2004，10(9)：1114-1119．(in Chinese)
［4］Wang T Y ，Wu K B．A revised simulated annealing algorithm for obtaining the minimum total tardiness in job shop scheduling problems［J］．International Journal Systems Science，2000，31(4)：537-542．
［5］Suresh R K ， Mohanasundaram K M．Pareto archived simulated annealing for job shop scheduling with multiple objectives［J］．The International Journal of Advanced Manufacturing Technology，2006，29(1/2)：184-196．
［6］Zhang J，Hu X M，Tan X，et al．Implementation of an ant colony optimization technique for job shop scheduling problem［J］．Transactions of the Institute of Measurement and Control，2006，28(1)：93-108．
［7］LI Yan-jun，WU Tie-jun．A nested hybrid ant colony algorithm for hybrid production scheduling problems［J］．ACTA Automation Sinica，2003，29(1)：95-101．(in Chinese)
［8］XIA Wei-jun ，WU Zhi-ming ，ZHANG Wei ，et al．Application of particle swarm optimization in the job-shop scheduling problem［J］．Journal of Shanghai Jiaotong University，2005，39(3)：381-385．(in Chinese)
［9］Tasgetiren M F，Sevkli M，Liang Y C，et al．Particle swarm optimization and differential evolution for job shop scheduling problem［J］．International Journal of Operational Research，2006，3(2)：120-135．
［10］Eusuff M M，Lansey K E．Optimization of water distribution network design using the shuffled frog leaping algorithm［J］．Journal of Water Sources Planning and Management，2003，129(3)：210-225．
［11］Eusuff M，Lansey K，Pasha F．Shuffled frog-leaping algorithm：a memetic meta-heuristic for discrete optimization［J］．Engineering Optimization，2006，38(2)：129-154．
［12］LIONG Shie-yui，Atiquzzaman Md．Optimal design of water distribution network using shuffled complex evolution［J］．Journal of Institution of Enginners，2004，44(1)：93-107．
［13］Hatem Elbehairy，Emad Elbeltagi，Tarek Hegazy，et al．Comparison of two evolutionary algorithms for optimziaiton of bridge deck repairs［J］．Computr-Aided Civil and Infrastructure Engineering，2006(21)：561-572．
［14］Elbeltagi E，Hegazy T，Grierson D．A modified shuffled frog-leaping optimization algorithm：applications to project management［J］．Structure and Infrastructure Engineering，2007，3(1)：53-60．
［15］Alireza Rahimi-Vahed，Ali Hossein Mirzaei.Solving a bi-criteria permutation flow-shop problem using shuffled frog-leaping algorithm［J］．Soft Computing，2007，12(5)：435-452．
［16］LUO Jian-ping, LI Xia. Improved shuffled frog leaping algorithm for solving TSP［J］．Journal of Shenzhen University Science and Engineering，2010，27(2)：173-179．

相似文献/References:

[1]潘长城,徐晨,李国.解全局优化问题的差分进化策略[J].深圳大学学报理工版,2008,25(2):211.
　PAN Chang-cheng,XU Chen,and LI Guo.Differential evolutionary strategies for global optimization[J].Journal of Shenzhen University Science and Engineering,2008,25(4):211.
[2]张重毅,刘彦斌,于繁华,等.CDA市场环境模型进化研究[J].深圳大学学报理工版,2010,27(4):413.
　ZHANG Zhong-yi,LIU Yan-bin,YU Fan-hua,et al.Research on the evolution model of CDA market environment[J].Journal of Shenzhen University Science and Engineering,2010,27(4):413.
[3]欧阳春娟,李霞,李斌.基于递进多目标蛙跳优化的LSB±K隐写算法[J].深圳大学学报理工版,2012,29(No.3(189-282)):224.[doi:10.3724/SP.J.1249.2012.03224]
　OUYANG Chun-juan,LI Xia,and LI Bin.A secure LSB plus-minus K steganography based on escalating multi-objective SFLA[J].Journal of Shenzhen University Science and Engineering,2012,29(4):224.[doi:10.3724/SP.J.1249.2012.03224]
[4]姜建国,周佳薇,郑迎春,等.一种双菌群细菌觅食优化算法[J].深圳大学学报理工版,2014,31(1):43.[doi:10.3724/SP.J.1249.2014.01043]
　Jiang Jianguo,Zhou Jiawei,Zheng Yingchun,et al.A double flora bacteria foraging optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(4):43.[doi:10.3724/SP.J.1249.2014.01043]
[5]蔡良伟,刘思麒,李霞,等.基于蚁群优化的正则表达式分组算法[J].深圳大学学报理工版,2014,31(3):279.[doi:10.3724/SP.J.1249.2014.03279]
　Cai Liangwei,Liu Siqi,Li Xia,et al.Regular expression grouping algorithm based on ant colony optimization[J].Journal of Shenzhen University Science and Engineering,2014,31(4):279.[doi:10.3724/SP.J.1249.2014.03279]
[6]宁剑平,王冰,李洪儒,等.递减步长果蝇优化算法及应用[J].深圳大学学报理工版,2014,31(4):367.[doi:10.3724/SP.J.1249.2014.04367]
　Ning Jianping,Wang Bing,Li Hongru,et al.Research on and application of diminishing step fruit fly optimization algorithm[J].Journal of Shenzhen University Science and Engineering,2014,31(4):367.[doi:10.3724/SP.J.1249.2014.04367]
[7]刘万峰,李霞.车辆路径问题的快速多邻域迭代局部搜索算法[J].深圳大学学报理工版,2015,32(2):196.[doi:10.3724/SP.J.1249.2015.02000]
　Liu Wanfeng,and Li Xia,A fast multi-neighborhood iterated local search algorithm for vehicle routing problem[J].Journal of Shenzhen University Science and Engineering,2015,32(4):196.[doi:10.3724/SP.J.1249.2015.02000]
[8]蔡良伟,程璐,李军,等.基于遗传算法的正则表达式规则分组优化[J].深圳大学学报理工版,2015,32(3):281.[doi:10.3724/SP.J.1249.2015.03281]
　Cai Liangwei,Cheng Lu,Li Jun,et al.Regular expression grouping optimization based on genetic algorithm[J].Journal of Shenzhen University Science and Engineering,2015,32(4):281.[doi:10.3724/SP.J.1249.2015.03281]
[9]王守觉,鲁华祥,陈向东,等.人工神经网络硬件化途径与神经计算机研究[J].深圳大学学报理工版,1997,14(1):8.
　Wang Shoujue,Lu Huaxiang,Chen Xiangdong and Zeng Yujuan.On the Hardware for Artificial Neural Networks and Neurocomputer[J].Journal of Shenzhen University Science and Engineering,1997,14(4):8.
[10]陈星宇,周展,黄俊文,等.基于关键词挖掘的客户细分方法[J].深圳大学学报理工版,2017,34(3):300.[doi:10.3724/SP.J.1249.2017.03300]
　Chen Xingyu,Zhou Zhan,Huang Junwen,et al.A keyword-based mining method for customer segmentation[J].Journal of Shenzhen University Science and Engineering,2017,34(4):300.[doi:10.3724/SP.J.1249.2017.03300]
[11]骆剑平,李霞.求解TSP的改进混合蛙跳算法[J].深圳大学学报理工版,2010,27(2):173.
　LUO Jian-ping and LI Xia.Improved shuffled frog leaping algorithm for solving TSP[J].Journal of Shenzhen University Science and Engineering,2010,27(4):173.

备注/Memo

备注/Memo:
收稿日期：2009-09-07；修回日期：2010-09-01
基金项目：国家自然科学基金资助项目（60772148）
作者简介：蔡良伟（1964-），男（汉族），广东省阳江市，深圳大学教授．E-mail：cailw@szu.edu.cn
更新日期/Last Update: 2010-11-08