计算机科学 ›› 2015, Vol. 42 ›› Issue (7): 68-73.doi: 10.11896/j.issn.1002-137X.2015.07.015
魏嘉银 秦永彬 许道云
WEI Jia-yin QIN Yong-bin XU Dao-yun
摘要： 针对置换Flow Shop调度问题,在对经典启发式算法进行研究的基础上,提出了一种用于求解此类问题的DRPFSP算法。算法首先对加工时间矩阵A进行数据标准化处理；然后通过引入一个概率矩阵P2×m和相应的降维函数fp(A)=PA,将含有m台机器的原问题转化为含2台机器的新问题；再运用Johnson算法对新问题进行求解得到一个调度序列π0；最后结合插入邻域快速评价法对π0进行处理以获得原问题的一个调度方案π。实验结果表明,相对于经典的启发式算法,DRPFSP算法能更有效地对置换Flow Shop调度问题进行求解。
| [1] Garey M R,Johnson D S,Sethi R.The Complexity of Flowshop and Jobshop Scheduling [J].Mathematics of Operations Research,1976,1(2):117-129 [2] Johnson S M.Optimal two-and three-stage production schedules with setup times included [J].Naval Research Logistics Quarterly,1954,1:61-68 [3] Campbell H G,Dudek R A,Smith M L.A heuristic algorithm for the n-job,m-machine sequencing problem[J].Management Science,1970,16(10):630-637 [4] Palmer D.Sequencing jobs through a multi-stage process in the minimum total time-a quick method of obtaining a near optimum [J].Operational Research Quarterly,1965,16(1):101-107 [5] Gupta J N.A functional heuristic algorithm for the flowshopscheduling problem [J].Operational Research Quarterly,1971,22(1):39-47 [6] Dannenbring D G.An evaluation of flow shop sequencing heuristics [J].Management Science,1977,23(11):1174-1182 [7] Nawaz M,Enscore J E E,Ham I.A heuristic algorithm for the m-machine,n-job flow-shop sequencing problem [J].OMEGA-the International Journal of Management Science,1983,11(1):91-95 [8] Kalczynski P J,Kamburowski J.On the NEH heuristic for minimizing the makespan in permutation flow shops [J].OMEGA-the International Journal of Management Science,2007,35:53-60(下转第107页)(上接第73页) [9] Kalczynski P J,Kamburowski J.An improved NEH heuristic to minimize makespan in permutation flow shops [J].Computers & Operations Research,2008,35(9):3001-3008 [10] Farahmand R S,Ruiz R,Boroojerdian N.New high performing heuristics for minimizing makespan in permutation flowshops [J].OMEGA-the International Jouranal of Management Science,2009,37:331-345 [11] Sioud A,Gravel M,Gagne C.A genetic algorithm for solving a hybrid flexible flowshop with sequence dependent setup times[C]∥2013 IEEE Congress on Evolutionary Computation (CEC).2013:2512-2516 [12] Wang X,Tang L.A tabu search heuristic for the hybrid flow-shop scheduling with finite intermediate buffers [J].Computers & Operations Research,2009,36(3):907-918 [13] Lin S W,Ying K C.Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems [J].International Journal of Production Research,2009,47(5):1411-1424 [14] Yagmahan B,Yenisey M M.A multi-objective ant colony system algorithm for flow shop scheduling problem[J].Expert Systems with Applications,2010,37(2):1361-1368 [15] Liao C J,Tjandradjaja E,Chung T P.An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem [J].Applied Soft Computing,2012,12(6):1755-1764 [16] Taillard E.Some effective heuristic methods for the flowshop sequencing problem[J].European Journal of Operational Research,1990,47:67-74 |
| No related articles found! |
|
||
首页