A Bacterial Evolutionary Algorithm for the Job Shop Scheduling Problem

以細菌演化演算法求解零工工廠問題

10.29977/JCIIE.200605.0001

陸冠群(Guan-Chun Luh)；李世威(Shih-Wei Lee)

零工工廠問題 ； 細菌演化演算法 ； 基因轉移 ； 利基法 ； bacterial evolutionary algorithm ； gene transfer ； job shop scheduling problem ； niche scheme

工業工程學刊

23卷3期（2006 / 05 / 01）

185 - 191

英文

零工工廠問題為最複雜且最困難的組合最佳化問題之一，其研究目的在於增加生產效率及降低製程時間，使能獲得最大利潤。此外，有研究顯示零工工廠問題一向是一種高難度的非線性規畫組合問題，因此需耗費許多時間解題。本文提出細菌演化演算法求解零工工廠問題的單目標多解排程，細菌演化演算法是一種最佳化方法，仿照細菌演化自然現象的特殊機制，並結合基因轉移及細菌突變運算元來增進最佳化的成效，本研究並使用利基法求得相同目標值但不同解的多種排程。最後，本研究引用多個為人所知的範例評價所提方法的功效。

The job-shop scheduling problem is one of the most complicated and well-known hardest combinatorial optimization problems. It's purpose is to improve the production efficiency and reduce the processing duration so as to gain profits as high as possible. In addition, it has been illustrated that job-shop scheduling is usually an NP-hard combinatorial problem and is therefore unlikely to be solvable in polynomial time. In this study, a bacterial evolutionary algorithm is proposed for finding multiple optimal solutions to the job-shop scheduling problem. Bacterial evolutionary algorithm is an optimization method that incorporates special mechanisms inspired by natural phenomena of microbial evolution. Gene transfer and bacterial mutation operators are incorporated to improve the performance of the proposed method. Moreover, niche scheme is employed to discover multiple solutions. Numerous well-studied benchmark examples were utilized to evaluate the effectiveness of the proposed approach.

1. Al-Hakim, L.(2001).An analogue genetic algorithm for solving job shop scheduling problems.Int. J. Prod. Res..
2. Baker, K. R(1994).Introduction to Sequencing and Scheduling.
3. Blum, C.(2003).Technical Report TR/IRIDIA/2003-01, IRIDIATechnical Report TR/IRIDIA/2003-01, IRIDIA,Belgium:Universite Libre de Bruxelles.
4. Coello Coello, C. A.,D. Cortés Rivera,N. Cruz Cortés(2003).Use of an artificial immune system for job shop scheduling.Lecture Notes in Computer Science.
5. Fisher, H.,G. L. Thompson,J. F. Muth(1963).Probabilistic learning combinations of local job-shop scheduling rules.Industrial Scheduling.
6. French, S(1982).Sequencing and Scheduling.
7. Garey, M.,D. Johnson,R. Sethi(1976).The complexity of flowshop and job shop scheduling.Mathematics of Operations Research.
8. Gen, M.,Y. Tsujimura,E. Kubota(1994).Solving job-shop scheduling problems by genetic algorithm.IEEE International Conference on Systems, Man, and Cybernetics, 'Human, Information, and Technology'.
9. Giffler, B.,G. L. Thompson(1963).Algorithm for solving production scheduling problems.Operation Research.
10. Goldberg, D. E.(1989).Genetic Algorithms in Search, Optimization and Machine Learning.
11. Gonçalves, J. F.,J. J. de Magalhães,M. G. C. Resende(2002).Technical ReportTechnical Report,AT&T Labs.
12. Hartwell, L. H.,L. Hood,M. L. Goldberg,A. E. Reynolds,L. M. Silver,R. C. Veres(2004).Genetic From Genes to Genomes.
13. Jain, A. S.,S. Meeran(1999).A State-of-the-Art Review of Job-Shop Scheduling Techniques.European Journal of Operations Research,113(2),390-434.
14. Lawrence, S.(1984).Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques.
15. Muth, J. F.,G. L. Thompson(1963).Industrial Scheduling.
16. Nawa, N. E.,T. Furuhashi(1999).Fuzzy system parameter discovery by bacterial evolutionary algorithm.IEEE Transactions on Fuzzy System.
17. Nawa, N. E.,T. Hashiyama,T. Furuhashi,Y. Uchikawa(1997).A study on fuzzy rules discovery using pseudo-bacterial genetic algorithm with adaptive operator.Proceedings of IEEE Int. Conf. on Evolutionary Computation.
18. Park, L.-J.,C. H. Park(1995).Genetic algorithms for job shop scheduling problems based on two representation schemes.Electronics Letters.
19. Passino, K. M.(2002).Biomimicry of bacterial foraging for distributed optimization and control.IEEE Control Systems Magazine,22(3),52-67.
20. Ponnambalam, S. G.,P. Aravindan,S. V. Rajesh(2000).A tabu search algorithm for job shop scheduling.The International Journal of Advanced Manufacturing Technology,16(10),765-771.
21. Redfield, R. J(2001).Do bacteria have sex?.Nature Reviews.
22. Steinhöfel, K.,A. Albrecht,C. K. Wong(1999).Two simulated annealing-based heuristics for the job shop scheduling problem.European Journal of Operational Research,118(3),524-548.
23. Ventresca, M.,B. M. Ombuki(2003).Technical reportTechnical report,Department of Computer Science, Brock University.
24. Wang, L.,D.-Z. Zheng(2002).A modified genetic algorithm for job shop scheduling.The International Journal of Advanced Manufacturing Technology,20(1),72-76.
25. Wang, W.,P. Brunn(2000).An effective genetic algorithm for job shop scheduling.Proceedings of Institute Mechanical Engineers, Part B.
26. Yamada, T.,R. Nakano(1997).Genetic algorithms for job shop scheduling problems.Proceedings of Modern Heuristic for Decision Support.
27. Yang, S.,D. Wang(2001).A new adaptive neural network and heuristics hybrid approach for job-shop scheduling.Computers & Operations Research
28. Yu, H.,W. Liang(2001).Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling.Computers & Industrial Engineering.

1. (2012).A genetic optimization algorithm and perceptron learning rules for a bi-criteria parallel machine scheduling.工業工程學刊,29(3),206-218.