Please use this identifier to cite or link to this item:
標題: 解決多目標流線型工廠排程問題之多軌跡搜尋演算法
A Multiple Trajectory Search for Multi-objective Flowshop Schedule Problem
作者: 陳伯鈞
Chen, Bo-Chun
關鍵字: 基因演算法
Genetic Algorithm
Local Search Algorithm
Flowshop Schedule Problem
total flow time
出版社: 資訊科學與工程學系所
引用: J. E. C. Arroyo and V. A. Armentano, “Genetic local search for multiobjective flowshop scheduling problems,” European Journal of Operational Research, vol. 167, no. 3, pp. 717–738, 2005. A. Allahverdi and T. Aldowaisan, “New heuristics to minimize total completion time in m-machine flowshops,” International Journal of Production Economics, vol. 77, pp. 71-83, 2002. T. P. Bagchi, Multiobjective Scheduling by Genetic Algorithms. Boston, MA: Kluwer, 1999. P C. Chang, J. C. Hsieh and S. G. Lin, “The Development of Gradual- priority Weighting Approach for the Multi-objective Flowshop Scheduling Problem,” International Journal of Production Economics, vol.79, pp.171-183, 2002. P.C. Chang, S. Chen and C. Liu , “Sub-population genetic algorithm with mining gene structures for multiobjective flowshop scheduling problems,” Expert Systems with Applications , vo1. 33, pp.762-771,2007. P.C. Chang, S.H. Chen ,C.Y. Fan and C.L.Chan, “Genetic algorithm integrated with artificial chromosomes for multi-objective flow shop scheduling problems,” Applied Mathematics and Computation, vol. 205, pp. 550–565, 2008. T.C. Chiang, H.C. Cheng and L.C. Fu, “NNMA: An effective memetic algorithm for solving multiobjective permutation flowshop scheduling problems,” Expert Systems with Applications, vol. 38, no. 5, pp. 5986–5999, 2011. H. G. Campbell, R. A. Dudek and M. L. Smith, “A heuristic algorithm form the n job, m machine sequence problem,” Management Science, vol. 16(10), pp. B630-B637, 1970. D. G. Dannenbring , “An evaluation of flowshop sequencing heuristics,”Management Science, vol. 23, no. 11, pp. 1174–1182, 1977. K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, pp. 182–197, 2002. J. M. Framinan and R. Leisten, ” An efficient constructive heuristic for flowtime minimisation in permutation flow shops,” OMEGA, vol. 31, pp. 311-317, 2003. M. Garey, D. S. Johnson and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Mathematical Methods of Operations Research, vol. 1, pp. 117–129, 1976. J. C. Ho, “Flowshop sequencing with mean flowtime objective,”European Journal of Operational Research, vol. 81(3), pp. 571-578, 1995. S.Y. Ho and J.H. Chen, “A GA-basedsystematic reasoning approach for solving traveling salesman problems using an orthogonal array crossover,” in Proceeding ofThe Fourth International IEEE Conference/Exhibition on High Performance Computing in Asia-Pacific Region, Beijing,China, pp. 659-663, 2000. H. Ishibuchi and T. Murata,“A multi-objective genetic local search algorithm and its application to flowshop scheduling,” IEEE Transactions on Systems, Man, and Cybernetics PartC, vol. 28, no. 3, pp. 392–403, 1998. E. Ignall and L.E. Schrage, “Application of branch and bound technique to some flow-shop problem,” Operations Research, vol. 13, pp. 400-412, 1964. S. M. Johnson, “Optimal two-and three-stage schedules with setup times included,” Naval Research Logistics Quarterly,vol.1 no. 1, pp.61-68, 1954. J. Knowles and D. Corne, “On metrics for comparing nondominated sets,” in Congress on Evolutionary Computation (CEC02), pp. 711–716, 2002. B. B. Li and L. Wang, “A hybrid quantum-inspired genetic algorithm for multi-objective flow shop scheduling,” IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, vol. 37, no. 3, pp. 576–591, 2007. G. Minella, R. Ruiz and M. Ciavotta, “A review and evaluation of multi-objective algorithms for the flowshop scheduling problem,”INFORMS Journal of Computing, vol. 20, pp. 451−471, 2008. M. Nawaz, E. Enscore and I. Ham, “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem,” Omega, vol. 11, no. 1, pp. 91–95, 1983. A. C. Nearchou, “The effect of various operators on the genetic search for large scheduling problems,” International Journal of Production Economics, vol. 88, no. 2, pp. 191–203, 2004. F. A. Ogbu and D. K. Smith, “Simulated annealing for the permutation flowshop problem,” Omega, vol. 19, no. 1, pp. 64–67, 1990. D. S. Palmer, “Sequencing jobs through a multistage process in the minimum total time: A quick method of obtaining a near-optimum,”Operational Research Quarterly, vol. 16, pp. 101–107, 1965. S. Parthasarathy and C. Rajendran , “Scheduling to minimize mean tardiness and weighted mean tardiness in flowshop and flowline-based manufacturing cell,” Computers and Industrial Engineering, vol. 34(2), PP. 531–546, 1998 . C. R. Reeves, “A genetic algorithm for flowshop scheduling,” Computers & Operations Research, vol. 22, no. 1, pp. 5–13, 1995. C. Rajendran, “Heuristics for scheduling in flowshop with multiple objectives,” European Journal of Operational Research, vol. 83, pp. 540−555, 1995. C. Rajendran and H. Ziegler, “An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs,”European Journal of Operational Research, vol. 103, pp. 129-138, 1997. C. Rajendran,H. Ziegler, “Ant-colony algorithms for permutation flowshopscheduling to minimize makespan/total flowtime of jobs,”European Journal of Operational Research,vol. 155(2), pp. 426-438, 2004. E. D. Taillard, “Robust Taboo Search for the Quadratic Assignment Problem,” Parallel Computing, vol. 17, pp. 443-455, 1991. E. Tailard, “Benchmarks for basic scheduling problems,” European Journal of Operational Research, vol. 64, pp. 278–285, 1993. J. T. Tsai, T. K. Liu and J. H. Chou, “Hybrid Taguchi-genetic algorithm for global numerical optimization,” IEEE Transactions on Evolutionary Computation, vol. 8, no. 4, pp. 365–377, 2004. L. Y. Tseng and Y. T. Lin, “A genetic local search algorithm for minimizing total flowtime in the permutation flowshop scheduling problem,”International Journal of Production Economics, vol. 127, pp.121-128, 2010. L. Y. Tseng and Y. T. Lin, “A hybrid genetic local search for the permutation flowshop scheduling problem,” European Journal of Operational Research, vol. 198, pp. 84-92, 2009. M.F. Tasgetiren, Y. -C. Liang, M. Sevkli, G. Gencyilmaz, “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem,” European Journal of Operational Research, vol. 177, pp. 1930-1947, 2007. T.K. Varadharajan and C. Rajendran. “A multi-objective simulatedannealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs,” European Journal of Operation Research, vol. 167, no. 3, pp. 772–795, 2005. D. S. Woo and H. S. Yim, “A heuristic algorithm for mean flowtime objective in flowshop scheduling,” Computers&Operational Research, vol. 25, pp. 175–182, 1998. Y. Zhang and X. Li, Q. Wang, “Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization,”European Journal of Operational Research, vol. 196, pp. 869-876, 2009.
摘要: 流線型工廠排程問題是NP-Hard裡的核心問題之一,在製造業生產線、軟體開發等領域有諸多應用。 本研究中使用混合式基因演算法來解決流線型工廠排程問題,針對目前許多演算法的缺點,我們提出了三點改善:1.加入了直交表(orthogonal array)交配(crossover)提高強化性(intensification);2.提出兩層架構,在各個區域有種子(seed)產生,比較不會錯過全域最佳解; 3.維持多樣性(diversification)。 我們應用本論文所提出的演算法於E.Taillard於1993所彙整的Taillard’s 標準測試題組(benchmark),並和其他演算法做一比較,並獲得不錯的成果。
The permutation flowshop scheduling problem is one of the core NP-hard problems with many applications filed such as, the industry production line and the software development. In this thesis, we propose a hybrid genetic local search algorithm to solve the multi-objective flowshop scheduling problem. The objectives are considered, namely, the makespan and the total flow time. Observing the weak points with some algorithms published in the literature, we developed our algorithm with two characteristics:1.Adding the orthogonal-array crossover operator to enhance the intensification. 2.We use two-layer genetic algorithm to search the solution space more thoroughly. 3.Maintaining diversification. We compare the proposed algorithm with other algorithms in the literature published on the benchmarks offered by Taillard’s 1993. The quality of solutions obtained by the proposed algorithm is competitive with other algorithms, whereas the computation time needed is more than that of other algorithms.
其他識別: U0005-0908201214030100
Appears in Collections:資訊科學與工程學系所



Show full item record
TAIR Related Article

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.