An Evolutionary Algorithm for Job Schedulind in Multimachine Environments

• Autorzy: Marcin Wawrzyniak
• Języki publikacji: EN

Abstrakty

EN

The random keys representation allows many different implementations of crossover operators. The best results of the two tested operators were obtained for the operator exchanging scopes of operations. It was proved that the introduction of the mechanism maintaining the population diversity allows to obtain lower makespans. During the simulations with the well-known benchmark problem MT10 with Cmax as the objective functions, the optimal solutions were found. It is worth mentioning that the proposed evolutionary algorithm does not use any properties of the objective functions (does not use any priority rules, does not create only active schedules). (fragment of text)

Słowa kluczowe

EN

Competitiveness; Algorithms

PL

Konkurencyjność; Algorytmy

• Czasopismo: Zeszyty Studiów Doktoranckich / Uniwersytet Ekonomiczny w Poznaniu. Wydział Ekonomii
• Rocznik: 2009
• Numer: nr 50
• Strony: 47--63

Twórcy

autor

Marcin Wawrzyniak

Bibliografia

• Adams J., Balas E., Zawack D., The sifting bottleneck procedure for job shop scheduling problem, Management Science, 34/1988, s. 391-401.
• Bean J., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6/1994, s. 154-160.
• Carlier J., Pinson E., An algorithm for solving the job-shop problem, Management Science, 35/1989, s. 164-176.
• Chan F.T.S., Chung S.H., Chan P.L.Y., An adaptive genetic algorithm with dominated genes for distributed scheduling problems, Expert Systems with Applications, 29/2005, s. 364-371.
• Essafia I., Matib Y., Dauzere-Peresc S., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem, Computers & Operations Research, 35/2008, s. 2599-2616.
• Goncalves J.F., Magalhaes Mendes F.F., Resende M., A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operational Research, 167/2005, s. 77-95.
• Huang K.L., Liao C.J., Ant colony optimization combined with taboo search for the job shop scheduling problem, Computers & Operations Research, 35/2008, s. 1030-1046.
• Kim K.W., Gen M., Yamazaki G., Hybrid genetic algorithm with fuzzy logic for re- source-constrained project scheduling, Applied Soft Computing, 2-3F/2003 s. 174-188.
• Kumar H., Srinivasan G., A genetic algorithm for job shop scheduling - A case study, Computers in Industry, 31/1996, s. 155-160.
• Mattfeld D., Bierwirth C., An efficient genetic algorithm for job shop scheduling with tardiness objectives, European Journal of Operational Research, 155/2004, s. 616-630.
• Park B.J., Choi H.R., Kim H.S., A hybrid genetic algorithm for the job shop scheduling problems, Computers & Industrial Engineering, 45/2003, s. 597-613.
• Pongcharoen P., Hicks C., Braiden P.M. Stewardson, D.J., Determining optimum genetic algorithm parameters for scheduling the manufacturing and assembly of complex products, International Journal of Production Economics, 78/2002, s. 311-322.
• Ponnambalam S.G., Jawahar B., Kumar S., Estimation of optimum genetic control parameters for job shop scheduling, International Journal of Advanced Manufacturing Technology, 19/2002, s. 224-234.
• Sakawa M., Kubota R., Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms, European Journal of Operational Research, 120/2000, s. 393-407.
• Steinhofel K., Albrecht A., Wong C.K., An experimental analysis of local minima to improve neighborhood search, Computers & Operations Research, 30/2003, s. 2157- 2173.
• Streeter M.J., Smith S.F., How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines, Journal of Artificial Intelligence Research, 26/2006, s. 247-287.
• Taillard E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64/1993, s. 278-285.
• Tanev I., Uozumi T., Morotome Y., Hybrid evolutionary algorithm-based real-world flexible job shop scheduling problem: application service provider approach, Applied Soft Computing, 5/2004, s. 87-100.
• Tsai C.F., Lin F.C., A new hybrid heuristic technique for solving job-shop scheduling problem, IEEE International Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, Lviv, Ukraine 2003.
• Wang C.S., Uzsoy R., A genetic algorithm to minimize maximum lateness on a batch processing machine, Computers & Operations Research, 29/2002, s. 1621-1640.
• Wang L., Zheng D.Z., An effective hybrid optimization strategy for job-shop scheduling problems, Computers & Operations Research, 28/2001, s. 585-596.
• Watanabe M., Ida K., Gen M., A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem, Computers & Industrial Engineering, 48/2005, s. 743-752.
• Yamada T., Nakano R., A genetic algorithm applicable to large-scale job-shop problems, Parallel Problem Solving from Nature, Brussels, Belgium 1992.
• Zhang C.Y., Li Y.Q., Rao P.G., Guan Z.L., A very fast TS/SA algorithm for the job shop scheduling problem, Computers & Operations Research, 35/2008, s. 282-294.