柔性作业车间多品种小批量调度算法研究

中国机械工程 ›› 2010, Vol. 21 ›› Issue (04): 424-429.

柔性作业车间多品种小批量调度算法研究

吴秀丽;李苏剑;杜彦华

北京科技大学,北京,100083

出版日期:2010-02-25 发布日期:2010-03-10
基金资助:
北京科技大学机械工程学院2008青年教师基金资助项目

Research on Batch Scheduling Problem in a Flexible Job Shop

Wu Xiuli;Li Shujian;Du Yanhua 

University of Science and Technology Beijing,Beijing,100083

Online:2010-02-25 Published:2010-03-10

摘要/Abstract

摘要：

提出一种多目标混合遗传算法(MIGA)，采用集成法同时解决柔性作业车间调度的两个子问题：机器分配问题和工序调度问题。MIGA在标准遗传算法的基础上采用随机权重法解决多目标问题，引入精英保留策略加速算法的收敛，集成小生境技术提高种群的多样性，基于扩展工序编码，按Makespan和安装准备成本最优对调度批分别解码。最后，用标准算例进行了算法验证，证明MIGA可以有效解决柔性作业车间多品种小批量调度问题。

关键词:

柔性作业车间；多品种小批量；调度；多目标混合遗传算法, 调度批

Abstract:

A multi-objective integrated genetic algorithm(MIGA) was proposed to solve both of the assignment of machines to corresponding operations and the scheduling of operations on assigned machines in flexible job scheduling problem at the same time.MIGA used random weights to convert the multi-objective problem to a single-objective problem. An operation-extended coding method was presented.The elitist strategy and the niche technology were integrated into the roulette selection operation to speed up the convergence and to improve the diversity of the population respectively.A new scheduling-batch oriented active decoding method was designed.Finally,some benthmark problems were experimented.The results prove that MIGA can solve mass variety and small batch scheduling problem in the flexible job shop effectively and efficiently. 

中图分类号:

TP18

吴秀丽, 李苏剑, 杜彦华.

柔性作业车间多品种小批量调度算法研究

[J]. 中国机械工程, 2010, 21(04): 424-429.

TUN Xiu-Li, LI Su-Jian, DU Pan-Hua.

Research on Batch Scheduling Problem in a Flexible Job Shop

[J]. China Mechanical Engineering, 2010, 21(04): 424-429.

参考文献

[1]Bruker P, Schlie R. Job- shop Scheduling with Multi-- purpose Machines[J]. Computing, 1990,45 (4) :369-375.
[2]Brandimarte P. Routing and Scheduling in a Flexible Job Shop by Tabu Search[J]. Annals of Operations Research,1993,41(3) :157-183.
[3]Mati Y, Rezg N, Xie X L. An Integrated Greedy Heuristic for a Flexible Job Shop Scheduling Problem[C]//2001 IEEE International Conference on Systems, Man, and Cybernetics. Tucson, AZ: IEEE, 2001 : 2534-2539.
[4]Hapke M. Pareto Simulated Annealing for Fuzzy Multi -- objective Combinatorial Optimization[J]. Journal of Heuristics,2000,6(3) :329-345.
[5]Rigao C. Tardiness Minimization in a Flexible Job Shop: a Tabu Search Approach[J]. Journal of Intelligent Manufacturing, 2004,15 (1) : 103-115.
[6]Dauzere- Peres S,Paulli J. An Integrated Approach for Modeling and Solving the General Multiprocessot Job- shop Scheduling Problem Using Tabu Search[J]. Annals of Operations Research, 1997, 70:281-306.
[7]Mastrolilli M, Gambardella L M. Effective Neighborhood Functions for the Flexible Job Shop Problem[J]. Journal of Scheduling, 2002,3 (1) : 3-20.
[8]孙志峻,乔冰,潘全科,朱剑英.具有柔性加工路径的作业车间批量调度优化研究[J].机械科学与技术,2002,21(3):348-350.
[9]Silva D L. An Introduction to Multiobjective Metaheuristics for Scheduling and Timetabling [M]. Nottingham : ISN Workshop, 2004.
[10]周明,孙树栋编著.遗传算法原理及应用[M],1999:203.
[11]Hyun C J,Kim Y,Kim Y K. A Genetic Algorithm for Multiple Objective Sequencing Problems in Mixed Model Assembly Lines [J]. Computers Operations Research, 1998,25 (7/8) : 675-690.
[12]Kacem I, Hammadi S, Borne P. Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job--shop Scheduling Problems [J]. IEEE Transactions on Systems, Man and Cybernetics, Part C, 2002,32 ( 1 ) : 408-419.
[13]夏蔚军[1],吴智铭[1].基于混合微粒群优化的多目标柔性Job—shop调度[J].控制与决策,2005,20(2):137-141. 1
[14]Kacem 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 ; 245-276.
[15]鞠全勇[1,2],朱剑英[2].多目标批量生产柔性作业车间优化调度[J].机械工程学报,2007,43(8):148-154.