[1]严洪森,万晓琴,熊福力.基于VNS-EM混合算法的两阶段装配流水车间调度[J].东南大学学报(自然科学版),2014,44(6):1285-1289.[doi:10.3969/j.issn.1001-0505.2014.06.033]
 Yan Hongsen,Wan Xiaoqin,Xiong Fuli.Two-stage assembly flow shop scheduling based on hybrid VNS-EM algorithm[J].Journal of Southeast University (Natural Science Edition),2014,44(6):1285-1289.[doi:10.3969/j.issn.1001-0505.2014.06.033]
点击复制

基于VNS-EM混合算法的两阶段装配流水车间调度()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
44
期数:
2014年第6期
页码:
1285-1289
栏目:
机械工程
出版日期:
2014-11-20

文章信息/Info

Title:
Two-stage assembly flow shop scheduling based on hybrid VNS-EM algorithm
作者:
严洪森万晓琴熊福力
东南大学自动化学院, 南京 210096; 东南大学复杂工程系统测量与控制教育部重点实验室, 南京 210096
Author(s):
Yan Hongsen Wan Xiaoqin Xiong Fuli
School of Automation, Southeast University, Nanjing 210096, China
Key Laboratory of Measurement and Control of Complex Systems of Engineering of Ministry of Education, Southeast University, Nanjing 210096, China
关键词:
两阶段装配 提前和拖期费用 变邻域搜索 类电磁机制
Keywords:
two-stage assembly earliness/tardiness cost variable neighborhood search electromagnetism-like mechanism
分类号:
TB491
DOI:
10.3969/j.issn.1001-0505.2014.06.033
摘要:
针对以最小化工件提前期和拖期惩罚费用加权和为目标的两阶段装配流水车间调度问题, 证明了工件之间的最优排序性质, 并将其嵌入优化算法中. 由于该问题的NP难性, 提出了一种变邻域类电磁机制(VNS-EM)混合算法. 该混合算法在类电磁机制(EM)算法的每一次迭代过程中嵌入改进的变邻域搜索(VNS)算法, 利用其较好的局部搜索能力对每代最优个体的邻域进行精细搜索, 从而提高解的质量. 仿真结果表明了算法的有效性.与VNS算法和EM算法相比较, 提出的VNS-EM混合算法能更好地兼顾算法的精度和求解速度.
Abstract:
To deal with the two-stage assembly flow shop scheduling problem with the objective of minimizing the weighted sum of earliness and tardiness penalties, the properties of optimal job sequences are proved and embedded in the optimization algorithm. In view of the NP-hardness of the problem, a hybrid VNS-EM(variable neighborhood search-electromagnetism-like mechanism)algorithm is proposed. The improved VNS is embedded in each iteration of the EM algorithm. With the help of the good local search ability of the VNS algorithm, the fine neighborhood search of the optimum individual can be carried out and the solution is improved. Simulation results demonstrate the effectiveness of the algorithm. Compared with the VNS algorithm and the EM algorithm, the proposed hybrid VNS-EM algorithm can obtain better balance between solution accuracy and convergence speed.

参考文献/References:

[1] Potts C N, Sevastjanov S V, Strusevich V A, et al. The two-stage assembly scheduling problem: complexity and approximation [J]. Operations Research, 1995, 43(2): 346-355.
[2] Lee C Y, Cheng T C E, Lin B M T. Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem [J]. Management Science, 1993, 39(5): 616-625.
[3] Allahverdi A, Al-Anzi F S. A PSO and a tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application [J]. Computers & Operations Research, 2006, 33(4): 1056-1080.
[4] Al-Anzi F S, Allahverdi A. A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times [J]. European Journal of Operational Research, 2007, 182(1): 80-94.
[5] Allahverdi A, Al-Anzi F S. The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time [J]. The International Journal of Advanced Manufacturing Technology, 2008, 37(1/2): 166-177.
[6] Radhakrishnan S, Ventura J A. Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times [J]. International Journal of Production Research, 2000, 38(10): 2233-2252.
[7] 陈伟达, 达庆利. 基于准时交货的Job Shop 多机调度 [J]. 东南大学学报:自然科学版, 1997, 27(3): 94-97.
  Chen Weida, Da Qingli. A multi-machine job-shop scheduling for minimizing the earliness and tardiness penalties [J]. Journal of Southeast University: Natural Science Edition, 1997, 27(3): 94-97.(in Chinese)
[8] Birble 瘙塁(·overI), Fang S C. An electromagnetism-like mechanism for global optimization [J]. Journal of Global Optimization, 2003, 25(3): 263-282.
[9] 姜建国, 刘永青, 刘梦楠, 等. 类电磁机制算法研究与改进 [J]. 计算力学学报, 2014, 31(1): 135-140.
  Jiang Jianguo, Liu Yongqing, Liu Mengnan, et al. Study on and improvement of electro-magnetism-like mechanism algorithm [J]. Chinese Journal of Computational Mechanics, 2014, 31(1): 135-140.(in Chinese)
[10] 韩丽霞. 求解约束优化问题的混沌类电磁算法 [J]. 电子科技大学学报, 2014, 43(2): 278-281.
  Han Lixia. Chaos electromagnetism-like algorithm for constrained optimization problem [J]. Journal of University of Electronic Science and Technology of China, 2014, 43(2): 278-281.(in Chinese)
[11] 高亮, 王晓娟, 魏巍, 等. 一种改进的类电磁机制算法 [J]. 华中科技大学学报:自然科学版, 2006, 34(11): 4-6.
  Gao Liang, Wang Xiaojuan, Wei Wei, et al. A modified algorithm for electromagnetism-like mechanism [J]. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2006, 34(11): 4-6.(in Chinese)
[12] Hansen P, Mladenovic N. Variable neighborhood search: principle and application [J]. European Journal of Operational Research, 2001, 130(3): 449-467.
[13] 熊福力, 严洪森. 基于跳跃辅助工作策略的混流装配线排产优化 [J]. 自动化学报, 2012, 38(2): 259-269.
  Xiong Fuli, Yan Hongsen. Optimally sequencing mixed-model assembly lines optimally with skip utility work strategy [J]. Acta Automatica Sinca, 2012, 38(2): 259-269.(in Chinese)
[14] 杨宏安, 齐亮亮, 李锦远, 等. 求解作业车间JIT调度问题的VNS/MP混合算法 [J]. 计算机集成制造系统, 2014, 20(2): 414-423.
  Yang Hongan, Qi Liangliang, Li Jinyuan, et al. Hybrid algorithm of VNS/MP for JIT job-shop scheduling problem [J]. Computer Integrated Manufacturing Systems, 2014, 20(2): 414-423.(in Chinese)

备注/Memo

备注/Memo:
收稿日期: 2014-05-29.
作者简介: 严洪森(1957—), 男, 博士, 教授, 博士生导师, hsyan@seu.edu.cn.
基金项目: 国家高技术研究发展计划(863计划)资助项目(2007AA04Z112)、国家自然科学基金资助项目(60934008, 50875046).
引用本文: 严洪森,万晓琴,熊福力.基于VNS-EM混合算法的两阶段装配流水车间调度[J].东南大学学报:自然科学版,2014,44(6):1285-1289. [doi:10.3969/j.issn.1001-0505.2014.06.033]
更新日期/Last Update: 2014-11-20