彈性工作排程問題是傳統工作排程問題的一種衍伸問題，而這些問題是有名的NP-hard問題。基因演算法是基於“適者生存”這種觀念的一種啟發式演算法，並且廣泛地應用在彈性工作排程問題上。
我們提出了一個改良的基因演算法，採用不同的策略來產生初始群族。此外，我們提出兩種有效的交配及突變運算子以便更有效的產生染色體。實驗結果顯示我們提出的基因演算法比以往的基因演算法來得有效率。

The Flexible Job-shop Scheduling Problem is a generation of the classical job-shop scheduling problem, and this kind of problems is a well-known NP-hard problem. Genetic Algorithm is one of heuristic algorithms which is based on concept of “the survival of the fittest ”and widely used for solving FJSP.
We propose an improved genetic algorithm that integrates different strategies for generating the initial population. In addition, two effective crossover and mutation operators are proposed to adapt the chromosome. Experiment results show that the proposed GA is more efficient than other GAs.

[1]Garey MR, Johnson DS, Sethi R, “The complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research 1976;1:117–29.
[2]E.Balas, “Machine scheduling via disjunctive graphs: an implicit enumeration algorithm,” Operations Research, vol. 17, pp. 941-957, 1969.
[3]Pinedo M., “Scheduling: theory, algorithms and systems,” Englewood cliffs, NJ: Prentice-Hall; 2002.
[4]Feige U., Scheideler C, “Improved bounds for acyclic job shop scheduling,” Proceedings of the 30th annual ACM symposium on the theory of computing (STOC ’98); 1998. p. 624–33.
[5]Jansen K, Mastrolilli M, Solis-Oba R, “Approximation algorithms for Flexible Job Shop Problems,” Lecture notes in computer science, vol.1776. Proceedings of the fourth Latin American symposium on theoretical informatics; Berlin: Springer. 2000. p. 68–77.
[6]Brandimarte P, “Routing and scheduling in a flexible job shop by tabu search,” Annals of Operations Research 1993;41:157–83.
[7]Paulli J, “A hierarchical approach for the FMS scheduling problem,” European Journal of Operational Research 1995;86(1):32–42.
[8]Barnes JW, Chambers JB, “Flexible Job Shop Scheduling by tabu search,” Graduate program in operations research and industrial engineering.Technical Report ORP 9609, University of Texas, Austin; 1996. _http://www.cs.utexas.edu/users/jbc/_.
[9]Vaessens RJM, Aarts EHL, Lenstra JK, “Job Shop Scheduling by local search,” COSOR Memorandum 94-05. Eindhoven University; 1994.
[10]Dauzere-Peres 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:281–306.
[11]Hurink J, Jurish B, Thole M, “Tabu search for the job shop scheduling problem with multi-purpose machines,” OR-Spektrum 1994;15:205–15.
[12]Mastrolilli M, Gambardella LM, “Effective neighbourhood functions for the flexible job shop problem,” Journal of Scheduling 1996;3:3–20.
[13]Chen H, IhlowJ, Lehmann C, “A genetic algorithm for flexible Job-shop scheduling,” IEEE international conference on robotics and automation, Detroit; 1999. p. 1120–5.
[14]Jia HZ, Nee AYC, Fuh JYH, Zhang YF,” A modified genetic algorithm for distributed scheduling problems,” International Journal of Intelligent Manufacturing 2003;14:351–62.
[15]Ho NB, Tay JC,” GENACE: an efficient cultural algorithm for solving the Flexible Job-Shop Problem,” IEEE international conference on robotics and automation 2004;1759–66.
[16]Kacem I, Hammadi S, Borne P, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems”, IEEE Transactions on Systems, Man, and Cybernetics, Part C 2002;32(1):1–13.
[17]J. H. Holland, “Adaption in Natural and Artificial Systems,” Cambridge, MA: The M.I.T.Press, 1975.
[18]Lee KM, Yamakawa T, Lee KM, “A genetic algorithm for general machine scheduling problems,” International Journal of Knowledge-Based Electronic 1998;2:60–6.
[19]F. Pezzella, G. Morganti, G. Ciaschetti, “A genetic algorithm for the Flexible Job-shop Scheduling Problem”, Computers & Operations Research, 2008, 35(2008). 3202-3212