摘要
柔性作业车间调度问题(FJSP)比传统作业车间调度问题的复杂性更高,其求解难度更大。本文利用蚁群和粒子群混合优化算法研究了柔性作业车间调度一类问题的求解方法,主要工作与创新点如下:
1、研究了蚁群粒子群混合优化算法在单目标柔性作业车间调度问题中的应用。首先,根据FJSP的求解特点,建立了主-从两级协调的蚁群粒子群混合算法结构。然后,对于主级蚁群优化算法构建了工序可选加工设备吸取图模型,设计了蚂蚁的解构造图和蚂蚁在工序可选加工设备间的转移概率;对于从级粒子群优化算法,采用位置矩阵的粒子表示方法,以粒子元素向量中优先权值的次序表示作业车间调度问题(JSP)中工件调度的次序,并在此基础上设计优先权值向量的解码方法。最后,以实验方式分析了蚁群粒子群混合优化算法中主要参数的取值问题。
2、研究了蚁群粒子群混合优化算法在能力约束和多目标柔性作业车间调度问题中的应用。针对上述两类柔性作业车间调度问题分别重新设计了蚁群优化算法中蚂蚁转移概率的局部启发式信息的计算和更新方式,使主级蚁群优化算法既能够在能力约束的柔性作业车间调度问题中处理能力约束条件,又能够在多目标柔性作业车间调度问题中实现设备总负荷和关键设备负荷最小两个优化目标。
3、研究了蚁群粒子群优化算法在多模式资源受限项目调度问题(MRCPSP)中的应用。首先,根据MRCPSP的求解特点,建立了主-从两级协调的蚁群粒子群混合算法结构。然后,对于主级蚁群优化算法设计了蚂蚁在任务间游历的转移概率和蚂蚁在任务执行模式间游历的模式优选概率;对于从级粒子群优化算法,采用基于任务的粒子表示方法,以任务优先权值标示任务的执行次序,并在粒子的解码中设计了任务优选概率的优选规则。最后,选用项目调度标准问题库(PSPLIB)中的测例,以实验的方式对蚁群粒子群混合优化算法中的主要参数取值进行优化。
Due to machine constraint, flexible job shop scheduling is much more complex than traditional job shop scheduling and even more difficult to be solved in view of optimization. In this dissertation, a hybrid of ant colony and particle swarm optimization algorithms is used to solve flexible scheduling problems such as flexible job shop scheduling. In this dissertation, the main work and innovations are as follows:
1. Flexible job shop scheduling problems with single objective are studied using the hybrid of ant colony and particle swarm optimization algorithms. First, A hybrid of ant colony and particle swarm optimization algorithms with master-slave structure is proposed based on the characteristic of flexible job shop scheduling problems to be solved. Then, an ant solution construction graph is presented and the transfer probability of ant between machines which can be selected to process job based on the extract graph of job processing machines for the ant colony algorithm at the master level. While, at the slave level, a decoding method is designed for particle based on the sequence of priority number in particle position matrix. Finally, the value of primary parameters in the hybrid algorithm is analyzed by experiments.
2. Capacity constrained and multi-objective flexible job shop scheduling problems are studied using the hybrid of ant colony and particle swarm optimization algorithm. The computing and updating method of local heuristic information in ant transfer probability is redesigned based on the characteristics of the problems above-mentioned. Therefore, not only the capacity constraints can be dealt with, but also the minimum of total machine load and bottle-neck machine load can be realized by the ant colony optimization algorithm at master level.
3. The mutli-mode resource-constrained project scheduling problems are studied using the hybrid of ant colony and particle swarm optimization algorithm. First, A hybrid of ant colony and particle swarm optimization algorithm with master-slave structure is proposed based on the characteristic of mutli-mode resource-constrained project scheduling problems to be solved. Then, the transfer probabilities of ant between tasks and between task-modes which can be selected to perform task based on the extract graph of task performing models for the ant colony algorithm at the master level. While, at the slave level, a decoding method including task-selecting probability is designed for particle based on the sequence of priority number in particle position vector . Finally, the value of primary parameters in the hybrid algorithm is analyzed by experiments based on the examples of project scheduling problem library (PSPLIB).
引文
[1]Jones,A. and Rabelo,J.C. Survey of Job Shop Scheduling Techniques, NISTIR, National Institute of Standards and Technology. Gaithersburg. MD. http://www.mel.nist.gov/,1998,1-17.
[2]唐国春.排序、经典排序和新型排序.数学理论与应用.1999(3).
[3]唐恒永,赵传立.排序引论科学出版社.北京.2002.
[4]LEE D Y,DICESARE F.Scheduling flexible manufacturing systems using Petri net and heuristic search[J].IEEE Transaction on Robotics and Automation,1994,10(2):123-132.
[5]Lageweg BJ,Lenstra JK & Rinnooy Kan AHG, Job-shop scheduling by implicit enumeration. Management Science,1977,24:441-450.
[6]Van Laarhoven PJM, EHL Aarts & JK Lenstra, Job shop scheduling by simulated annealing, Operations Research,1992,40:113-125.
[7]E.Taillard, Parallel taboo search techniques for the job-shop scheduling problem. ORSA Journal of Computing,1994,16:108-117.
[8]Dell’Amico M, Trubian M, Applying tabu search to the job shop scheduling problem, Annals of Operations Research, 1993,40:231-252.
[9]E.Nowicki, C. Smutnicki. A fast taboo search algorithm for the job-shop problem, Management Science, 1996,42:797-813.
[10]Aarts EHL,Van Laarhoven PJM, Lenstra JK & Ulder NIJ,A computational study of local search algorithms for job-shop scheduling, ORSA Journal of Computing,1994,6:118-125.
[11]Leticia Cagnina, Susana Esquivel, Raul Gallard. Particle swarm optimization for sequencing problems: a case study. Proceedings of 2004 Congress on Evolutionary Computation, Oregon, Porland,2004,536-540.
[12]M.Kolonko, Some new results on simulated annealing applied to the job shop scheduling problem, European Journal of Operational Research,1999,113:123-136.
[13]R.M.Aiex,S.Binato & M.G.C.Resende, Parallel GRASP with path-relinking for job shop scheduling, Parallel Computing,2003,29:393-430.
[14]F.Pezzella, E.Merelli, A tabu search method guided by shifting bottleneck for thejob shop scheduling problem, European Journal of Operational Research, 2000,120:297-310.
[15]BRUKER P,SCHLIE R.Job-shop scheduling with multipurpose machines[J].Computing,1990.45(4):369-375.
[16]夏蔚军,吴智铭.基于混合微粒群优化的多目标柔性Job-shop调度.控制与决策, 2005,20:137-141.
[17]孙志峻,朱剑英.具有柔性加工路径的作业车间智能优化调度.机械科学与技术[J],2001,20(6):931-933.
[18]HOLSAPPLE W,JAC0B V S,PAKATH R and ZAVERI JS.A genetics-based hybrid scheduler for generating static schedules in flexible manufacturing contexts[J].IEEE Transaction on Systems,Man and Cybernetics,1993,23(4):953-972.
[19]姜思杰,徐晓飞,李全龙.基于遗传优化算法求解作业车间调度问题[J].计算机集成制造系统-CIMS,2002,8(3):229-232.
[20]姜思杰,张付亮,王孔茂.基于遗传和禁忌算法求解一类车间调度问题[J].计算机集成制造系统-CIMS,2003,9(11):984-988.
[21]Chen, H., Ihlow, J., and Lehmann, C., A genetic algorithm for flexible job-shop scheduling, In Proceedings of IEEE International Conference on Robotics and Automation, 2,1120–1125, 1999.
[22]Mesghouni K., Hammadi S., Borne P., Evolution programs for job-shop scheduling, In Proc. IEEE International Conference on Computational Cybernetics and Simulation, 1,720-725.,1997.
[23]Kacem I., Hammadi S. and Borne P., Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, In IEEE Transactions on Systems, Man and Cybernetics, 2002,32(1), 1-13.
[24]杨晓梅,曾建潮.遗传算法求解柔性job shop调度问题[J].控制与决策,2004,19(10):1197-1200.
[25]F. Pezzella, G. Morganti, G. Ciaschetti. A genetic algorithm for the flexible job-shop scheduling problem,Computers & Operations Research Accepted Manuscript.
[26]Nhu Binh Ho, Joc Cing Tay , Edmund M.-K. Lai. An effective architecture for learning and evolving flexible job-shop schedules European Journal of Operational Research 2006,4(7),316–333.
[27]Zhang, H. and Gen, M., Multistage-based genetic algorithm for flexible job-shop scheduling problem. Journal of Complexity International, 11, 223-232, 2005.
[28]P.Brandimarte, Routing and Scheduling in a flexible job shop by taboo search, Annals of Operations Research,1993,41:157-183.
[29]L.F.Tung, L. Li&R.Nagi, Multi-objective scheduling for the hierarchical control of flexible manufacturing systems, The International Journal of Flexible Manufacturing Systems, 1999, 11:379-409.
[30]Dauzère-Pérès S, Paulli J. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research 1997; 70(3): 281-306.
[31]M.Mastrolilli, L .M .Gambardella, Effective neighborhood functions for the flexible job shop problem, Journal of Scheduling,2000,3(1):3- 20.
[32]Jurisch B. Scheduling jobs in shops with multi-purpose machines. PhD Dissertation, Fachbereich Mathematik/Informatik, Universitat Osnabruck, 1992.
[33]E.Hurink, B.Jurisch & M.Thole, Tabu search for the job shop scheduling problem with multi-purpose machines, Operations Research Spektrum,1994,15:205-215.
[34]Wu Z, Weng M-X. Multiagent scheduling method with earliness and tardiness objectives in flexible job shops. IEEE Transactions on System, Man, and Cybernetics-Part B 2005;35(2):293-301.
[35] MASTROLILLI M,GAMBARDELLA L M.Effective neighborhood functions for the flexible job shop problem[J].Journal of Scheduling,2002,3(1):3-20.
[36] Kacem I,Slim H,Pierre B.Pareto—Optimality Approach for Flexible Job—Shop Scheduling Problems:Hybridization of Evolutionary Algorithms and Fuzzy Logic.Mathematics and Computers in Simulation,2002,60(3-5):245-276.
[37]吴秀丽,孙树栋,余建军,张红芳.多目标柔性作业车间调度优化研究[J].计算机集成制造系统,2006,12(5):731-736.
[38]Pinedo M.Scheduling theory ,Algorithms,and Systems[M].Prentice Hall,Second Edition,2002.
[39]Li F, Zhu Y,Yin C.Fuzzy Programming for Multiobjective Fuzzy Job Shop Scheduling with Alternative Machines through Genetic Algorithms.The Proceedings of 2005 International Conference on Natural Computation,2005,992-1004.
[40]吴秀丽,孙树栋,杨展,蔡志强.面向工件的多目标柔性Job Shop调度问题研究[J].计算机集成制造系统, 2006,24(4):477-481.
[41]卢冰原,陈华平,古春生,谷峰.模糊环境下的柔性工作车间调度模型的研究[J].运筹与管理,2004,13(6):157-160.
[42]袁坤,朱剑英,王细洋.基于遗传算法的模糊目标柔性作业车间调度问题,机械科学与技术[J]. 2006,25(10):1135-1138.
[43]庞哈利.柔性Job shop集成化计划调度模型及其求解算法.控制与决策[J],2003,18(1):34-39.
[44]MATI Y,REZG N,XIE X L.An integrated greedy heuristic for a flexible job shop scheduling problem[A].The Proceedings of IEEE International Conference on Systems,M an,and Cybernetics[C].Piscataway,NJ,USA:IEEE,2001.2534-2539.
[45]HAPKE M.Pareto simulated annealing for fuzzy multi-objective combinatorial optimization[J].Journal of Heuristics,2000,6(3):329-345.
[46]Dorigo,M.,Maniezzo,V.,and Colomi,A. The Ant System : An autocatalytic optimizing process. Technical Report 1991-016 Revised, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy.
[47]Zlochin M. and Dorigo M. Model-based search for combinatorial optimization: A comparative study to appear in Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature(PPSN'2002).
[48]Gutjahr W.J. A graph-based ant system and its convergence, Future Gener.Comput.Syst.2000,16(8):873-888.
[49]Zlochin M.,Birattari M.,Meuleau N.,Dorigo M.Model-based search for combinatorial optimization. Technical ReportTR/IRIDIA/2001-15,IRIDIA, Universit’e Libre de Bruxelles.
[50]Dorigo M.,Zlochin M.,Meuleau N.,Birattari M. Updating ACO pheromones using Stochastic Gradient Ascent and Cross-Entropy methods ,in Proceedings of the Evo Workshops 2002,LNCS 2279,pp.21-30,Springer.
[51]王笑蓉.蚁群优化的理论模型及其在生产调度中的应用研究:[博士学位论文].杭州:浙江大学, 2003.
[52]Stutzle.T. and Hoos,H.H. The MAX-MIN ant system and local search for the traveling salesman problem. In Proceedings of ICEC’97-1997 IEEE 4th International Conference on Evolutionary Computation, 1997,308-313. IEEE Press, Piscataway, NJ.
[53]Stutzle,T. and Hoos,H.H. MAX-MIN Ant System. Future Generation Computer Systems, 2000,16(8):889-914.
[54]Quinlan, J. Combining instance-based and model-based learning. In Proceedings of the Tenth International Conference on Machine Learning, 1993,236-243.Morgan Kaufmann Publishers, San Mateo,CA.
[55]Stutzle T. and Dorigo M., A short convergence proof for a class of ant colonyoptimization algorithms. IEEE Transactions on Evolutionary Computation, 2002,6(4):358-365.
[56]Gambardella,L.M. and Drigo, M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. In Prieditism, A. and Russell, S., editors, Proceedings of the Twelfth International Conference on Machine Learning(ML-95), 1995,pp: 252-260. Morgan Kaufmann Publishers, Palo Alto, CA.
[57]Bullnheimer B., Hartl R.F, Strauss C. A new rank based version of the ant system: a computational study. Central European Journal for Operations Research and Economics, 1999,7(1):25-38.
[58]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展. 1999,26(10):1240-1245.
[59]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报. 2001,24(12):1328-1333.
[60]王颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报. 2002,14(1):32-33.
[61]覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制. 2002,31(3):198-201.
[62]Bauer,B. Bullnheimer,R.F, Hartl,C. Strauss, An ant colony optimization approach for the single machine total tardiness problem, in: Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, Piscataway, NJ, 1999,1445-1450.
[63]Merkle D. and Middendorf M. Ant colony optimization with global pheromone evaluation for scheduling a single machine. Applied Intelligence, 2003,18: 105-111.
[64]陈义保,姚建初,钟毅芳,周济.基于蚁群系统的工件排序问题的一种新算法,系统工程学报, 2002,17(5):476-480.
[65]Stutzle, T. An ant approach to the flow shop problem, in: Proceedings of European Congress on Intelligent Techniques and Soft Computing(EUFIT’98), Aachen, Germany, 1998,1560-1564.
[66]Zwaan der and Marques C. Ant colony optimization for job shop scheduling. In Proceedings of the Third Workshop on Genetic Algorithms and Artificial Life (GAAL 99).
[67]Reynold C W. Flock, herds and schools: a distributed behavioral model, Computer Graphics, 1987,21(4):25-34.
[68]Hepper F, U Grenander. A stochastic nonlinear model for coordinated bird flocks,In S Krasner Ed. The Ubiquity of Chaos, AAAS Publications, Washington DC, 1990.
[69]Shi Y, Eberhart R. A modified particle swarm optimizer[A], IEEE Int. Conf. on Evolutionary Computation[C], Piscataway, NJ, IEEE Service Center, 1998, 69-73.
[70]Clere M and Kennedy J. The Particle Swarm: Explosion, Stability and Convergence in a Multi-Dimensional Complex Space[J], IEEE Transaction on Evolutionary Computation, 2002,6(1):58-73.
[71]Ozcan E, Mohan C. Particle swarm optimization: Surfing the waves[A], Proc of the Congress on Evolutionary Computation[C], Washington DC, 1999, 1939-1944.
[72]Trelea I C. The particle swarm optimization algorithm: convergence analysis and parameter selection[J], Information Processing Letters, 2003, 85, 317-325.
[73]Angelin P J. Evolutionary optimization versus particle swarm optimization: Philosophy and performance difference [A], Proc of the 7th Annual Conf. on Evolutionary Programming [C], Gemany: Springer, 1998,601-610.
[74]Suganthan P N. Particle swarm optimizer with neighborhood operator [A]. Proc. Of the Congress on Evolutionary Computation [C], Washington DC, 1999, 1958-1962.
[75]Kennedy J. Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance [A], Proceedings of IEEE Congress on Evolutionary Computation [C], Piscataway, NJ: IEEE Service Center, 1999,1931-1938.
[76]Kenndy J, Mendes R. Population structure and particle swarm performance [A], Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2002) [C], Honloulu, HI USA, 2002,2,1671-1676.
[77]Riget J, Vesterstram J S. A diversity-guided particle swarm optimization the ARPSO, EVALife Technical Report no. 2002-02.
[78]Lovbierg M, Krink T. Extending particle swarms with self-organized criticality [A], Proceedings of the Fourth Congress on Evolutionary Computation [C], Honolulu, HI USA, 2002,1588-1593.
[79]Krink T, Vesterstrom J S, Riget J. Particle swarm optimization with spatial particle extension [A], Proceedings of the Fourth Congress on Evolutionary Computation [C], Honolulu, HI USA, 2002,2,1474-1479.
[80]Angeline P J. Using selection to improve particle swarm optimization [R]. IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, 1998.
[81]Lovbierg M, Rasmussen T K, Krink T. Hybrid particle swarm optimizer with breeding and subpopulations [A], Proceedings of the Genetic and EvolutionaryComputation Conference [C], San Francisco, California, 2001,469-476.
[82]高鹰,谢胜利.基于模拟退火的粒子群优化算法[J],计算机工程与应用, 2004,1,47-50.
[83]高鹰,谢胜利.免疫粒子群优化算法[J],计算机工程与应用, 2004,6,4-6.
[84]吕振肃,侯志荣.自适应变异的粒子群优化算法[J],电子学报, 2004,32(3):416-420.
[85]李炳宇,萧蕴诗,吴启迪.一种基于粒子群算法求解约束优化问题的混合算法[J],控制与决策,2004,19(7):804-806.
[86]Eberhart R, Kennedy J. Discrete binary version of the particle swarm algorithm [A], Proc. IEEE Int. Conf. on Systems, Man and Cybernetics [C], Orlando, 1997, 4104-4108.
[87]Hu X, Eberhart R C, Shi Y. Swarm intelligence for permutation optimization: a case study on n-queens problem [A], Proceedings of the IEEE swarm intelligence symposium 2003 [C], Indianapolis, Indiana, USA, 2003,243-246.
[88]Eberhart R C, Kennedy J. A new optimizer using particle swarm theory [A], Proc. On 6th International Symposium on Micro-machine and Human Science [C], Piscataway NJ: IEEE Service Center, 1995, 39-43.
[89]Ray T, Liew K M. A swarm with an effective information sharing mechanism for unconstrained and constrained single objective optimization problems [A], Proc. IEEE Int. Conf. on Evolutionary Computation [C], Seoul, 2001, 75-80.
[90]Robinson J, Sinton S, Rahmat S. Particle swarm, genetic algorithm, and their hybrids: optimization of a profiled corrugated horn antenna [A], 2002 IEEE Antennas and Propagation Society International Symposium and URSI National Radio Science Meeting [C], USA: Sun Automo, TX,2002,1,314-317.
[91]Ciuprina G, Ioan D, Munteanu I. Use of intelligent-particle swarm optimization in Electro-magnetic [J], IEEE transactions on magnetics, 2002,38(2):1037-1040.
[92]Abido M A. Optimal power flow using particle swarm optimization [J], Electical Power and Energy Systems, 2002,24,563-571.
[93]董颖,唐加福,许宝栋,汪定伟.一种求解非线性规划问题的混合粒子群算法[J],东北大学学报, 2003,24(12):1141-1144.
[94]李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J],系统工程理论与实践, 2004,4:130-135.
[95]李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究[J],计算机学报, 2004,27(7):897-903.
[96]万福才,汪定伟,李彦平.微粒群优化算法在相关新产品组合投入的应用[J],控制与决策, 2004,19(5):520-524.
[97]齐洁,汪定伟.求解网路广告资源优化模拟的改进微粒群算法[J],控制与决策, 2004,19(8):881-884.
[98]Jerald.J, Asokan.P, Prabaharan.G, et al. Scheduling optimization of flexible manufacturing systems using particle swarm optimization algorithm. Advanced Manufacturing Technology. 2004.
[99]Leticia Cagnina, Susana Esquivel, Raul Gallard. Particle swarm optimization for sequencing problems: a case study. Proceedings of 2004 Congress on Evolutionary Computation, Oregon, Portland, 2004, 536-540.
[100]Xia weijun, Wu zhiming, Zhang wei, et al. A new hybrid optimization algorithm for the job-shop scheduling problem. Proceedings of the 2004 American Control Conference, Boston, Massachusette. 2004, 5552-5557.
[101]Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperation agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1): 29-41.
[102]Botee H M, Bonabeau E. Evolving ant colony optimization. Advances in Complex System, 1998, 1(2): 149-159.
[103]段海滨.蚁群优化算法原理及其应用.科学出版社, 2005,12.
[104]Carlisle, A. and Dozier, G. An off-the-shelf PSO. Proceedings of the workshop on Particle Swarm Optimization, Indianaplis, IN,2001,1-6.
[105]孙志峻,朱建英.具有柔性加工路径的作业车间智能优化调度[J],机械科学与技术, 2001,20(6):931-933.
[106]张丽平.粒子群优化算法的理论及实践:[博士学位论文].杭州:浙江大学, 2005.
[107]张维存,郑丕谔,吴晓丹.基于主-从遗传算法求解柔性调度问题[J],计算机集成制造系统, 2006,12(8):1241-1245.
[108]Sprcher A, Drexl A. Mutli-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm[J]. European Journal of Operational Research. 1998,107:431-450.
[109]Jirachai Buddhakulsomsiri, David S. Kim. Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting[J]. European Journal of Operational Research. 2006,178:374-390.
[110]Mori M, Tseng CC. A genetic algorithm for multi-mode resource constrained project scheduling problem [J]. European Journal of Operational Research,1997,100:134-141.
[111]Rainer Kolish, S?nke Hartmann. Experimental investigation of heuristics for resource-constrained project scheduling: An update[J]. European Journal of Operational Research, 2006, 174: 23-37.
[112]Kolish R, Sprecher A. PSPLIB-a project scheduling problem library[J]. European Journal of Operational Research, 1996, 96: 205-216.
[113]Sprecher A, Kolisch R, Drexl A. Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 1995,80: 94-102.
[114]刘士新,王梦光,聂义勇.多执行模式资源受限工程调度问题的优化算法[J].系统工程学报, 2001, 16(1): 55-60.