期刊文献+

柔性作业车间调度问题的集成启发式算法 被引量:12

Integrated Heuristic Algorithm for Flexible Job-shop Scheduling Problems
下载PDF
导出
摘要 柔性作业车间调度问题,包括路径分配和加工排序2大子问题,是组合优化理论和实际生产管理的重要研究方向。作为传统作业车间调度的扩展,柔性作业车间调度问题的内在复杂性(强NP-Hard)使得传统的最优化方法难以有效求解。文章针对以多目标权重和最优为目标的柔性作业车间调度问题,提出基于过滤定向搜索的集成启发式算法,设计改进了节点分枝策略和局部/全局评价函数,能同时解决2大子问题。通过实例仿真,对算法性能进行比较分析和评价,结果表明了算法的可行性和有效性。 Flexible job-shop scheduling problem, containing routing sub-problem and sequencing sub-problem, is an important issue in both fields of combinatorial optimization and production operations. Being an extension of the classical job-shop scheduling problem, it presents additional complexity(NP-hard in strong sense), which makes traditional optimization approaches difficult to achieve an optimal solution in reasonable computational time. In this paper, a filtered-beam-search based heuristic algorithm is proposed to solve the flexible job-shop scheduling problem with the objective of optimal weighted sum of multiple measure performances. The proposed algorithm makes improvement in the generation procedures of branches and the local/global evaluation functions, which makes it possible to solve two sub-problems, the performance of the proposed algorithm is evaluated and compared with those of other representative approaches through simulations, and the results demonstrate the feasibility and efficiency of the proposed algorithm.
出处 《计算机工程》 CAS CSCD 北大核心 2008年第1期256-258,共3页 Computer Engineering
基金 国家自然科学基金资助项目(60574054) 2006新世纪优秀人才支持计划基金资助项目
关键词 柔性作业车间调度 过滤定向搜索 启发式方法 flexible job-shop scheduling filtered beam search heuristic algorithm
  • 相关文献

参考文献5

  • 1Xia Weijun,Wu Zhiming.An Effective Hybrid Optimization Approach for Multi-objective Flexible Job-shop Scheduling Problems[J].Computers & Industrial Engineering,2005,48(2):409-425.
  • 2庞哈利.柔性Job shop集成化计划调度模型及其求解算法[J].控制与决策,2003,18(1):34-39. 被引量:11
  • 3Kacem,I,Hammadi S,Borne P.Pareto-optimality Approach for Flexible Job-shop Scheduling Problems:Hybridization of Evolutionary Algorithms and Fuzzy Logic[J].Mathematics and Computers in Simulation,2002,60(3/5):245-276.
  • 4Sabuncuoglu I,Bayiz M.Job Shop Scheduling with Beam Search[J].European Journal of Operational Research,1999,118(2):390-412.
  • 5Mastrolilli M,Gambardella L M.Effective Neighbourhood Functions for the Flexible Job Shop Problem[J].Journal of Scheduling,2002,3(1):3-20.

二级参考文献11

  • 1[1]Conwey R W, Maxwell W L, Miller L W. Theory of Scheduling[M]. Massachusetts: Addision-Wesley,1967.
  • 2[2]Adams J, Balas E, Uzsoy R. The shifting bottleneck procedure for job shop scheduling[J]. Mgmt Sci,1988,34(3):391-401.
  • 3[3]Lourenco H R. Job shop scheduling: Computational study of local search and large step optimization methods[J]. Eur J Opns Res,1995,83:347-364.
  • 4[4]Chen I J, Chung C H. Effects of loading and routing decisions on performance of flexible manufacturing systems[J]. Int J Prod Res,1991,29(11):2209-2225.
  • 5[5]Hutchision J, Leong K, Snyder D, et al. Scheduling approach for random job shop flexible manufacturing systems[J]. Int J Prod Res,1991,29(5):1053-1067.
  • 6[6]Jiang J C, Hsiao W C. Mathematical programming for the scheduling problem with alternate process plans in FMS[A]. Proc 16th ICC IE[C].Ashikaga,1993.368-371.
  • 7[7]LogendranR,SonthinenA.A tabu search-basedapproach for scheduling job-shop type flexible manufacturing systems[J]. J Opl Res,1997,48(3):264-277.
  • 8[8]Dueck G, Scheuer T. Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing[J]. J Comput Physics,1990,90:161-175.
  • 9[9]Althofer I, Koschnick K U. On the convergence of "Threshold Accepting"[J]. Appl Math Optim,1991,24:183-195.
  • 10[10]Lawrance D. Handbook of Genetic Algorithms[M]. New York: Van Norstrand Reinhold,1991.

共引文献10

同被引文献110

引证文献12

二级引证文献25

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部