BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Chung Chia-Shin (Cleveland State Univesity), Flynn James (Cleveland State Univesity), Rom Walter (Cleveland State Univesity), Staliński Piotr (Wyższa Szkoła Biznesu - National Louis University)
Tytuł
A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems
Źródło
Journal of Entrepreneurship, Management and Innovation (JEMI), 2012, vol. 8, nr 2, s. 26-43, tab., bibliogr. 22 poz.
Tytuł własny numeru
Contemporary Management Concepts
Słowa kluczowe
Algorytmy genetyczne, Optymalizacja, Metody heurystyczne
Genetic algorithms, Optimalization, Heuristics methods
Uwagi
streszcz., summ.
Abstrakt
Permutacyjny problem przepływowy (ang. permutation flowshop problem) z m maszynami i n zadaniami oraz minimalizacją sumy opóźnień jest znanym zagadnieniem z zakresu szeregowania zadań. Zagadnienie to należy do kategorii NP-trudnych problemów optymalizacji kombinatorycznej. Metoda podziału i ograniczeń (ang. branch and bound), popularne podejście do rozwiązania problemu, doświadcza trudności (biorąc pod uwagę czas potrzebny dla znalezienia rozwiązania optymalnego) gdy n przekracza 20. W niniejszej pracy, proponujemy algorytm genetyczny GA dla rozwiązywania zagadnienia dla dużych wartości n. Przytaczamy wyniki obszernego studium obliczeniowego, które porównuje funkcjonowanie algorytmu GA z metodą podziału i ograniczeń oraz metodami heurystycznymi - znanym algorytmem NEH i heurystyką lokalnego przeszukiwania LH. Rezultaty obliczeniowe wskazują, że metoda LH jest wydajnym algorytmem heurystycznym i że metoda GA oferuje możliwość poprawy wyników w porównaniu z algorytmem LH. (abstrakt oryginalny)

The m-machine, n-job, permutation flowshop problem with the total tardiness objective is a common scheduling problem, known to be NP-hard. Branch and bound, the usual approach to finding an optimal solution, experiences difficulty when n exceeds 20. Here, we develop a genetic algorithm, GA, which can handle problems with larger n. We also undertake a numerical study comparing GA with an optimal branch and bound algorithm, and various heuristic algorithms including the well known NEH algorithm and a local search heuristic LH. Extensive computational experiments indicate that LH is an effective heuristic and GA can produce noticeable improvements over LH. (original abstract)
Pełny tekst
Pokaż
Bibliografia
Pokaż
  1. Armentano, V. and Ronconi, D. (1999). Tabu search for total tardiness minimization in flowshop scheduling problems. Computers & Operations Research 26, 219-235.
  2. Arroyo, J., and Armentano, V. (2005). Genetic local search for multi-objective flowshop scheduling problems. European Journal of Operational Research 167, 717-738.
  3. Chung, C.S., Flynn, J., and Kirca, O. (2002). A branch and bound algorithm to minimize the total flowtime for m- machine permutation flowshop problems. International Journal of Production Economics 79, 185-196.
  4. Chung, C.S., Flynn, J., and Kirca, O. (2006). A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems. European Journal of Operational Research, 174, 1-10.
  5. Etiler, O., Toklu, B., Atak, M., and Wilson, J. (2004). A genetic algorithm for flow shop scheduling problems. Journal of the Operational Research Society 55, 830-835.
  6. Framinan, J., Leisten, R., and Ruiz-Usano (2005). Comparison of heuristics for flowtime minimization in permutation flowshops. Computers & Operations Research 32, 1237-1254.
  7. Holland, H. (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.
  8. Kim, Y.D. (1993). Heuristics for Flowshop Scheduling Problems Minimizing Mean Tardiness. J. Operational Research Society 44, 19-28.
  9. Kim, Y.D. (1995). Minimizing tardiness in permutation flowshops. European Journal of Operational Research 85, 541-555.
  10. Koulamas, C. (1994). The total tardiness problem: review and extensions. Operations Research 42, 1025-1040.
  11. Lawler, E. (1997). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics 1, 331-342.
  12. Nawaz, M. ,Enscore, E., and Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flowshop scheduling problem, OMEGA 11, 91-95.
  13. Ombuki, B., and Ventresca, M. (2004). Local search genetic algorithms for the job shop scheduling problem. Applied Intelligence 21, 99-109.
  14. Pinedo, M. (2002). Scheduling, 2nd Edition, Prentice-Hall, New Jersey.
  15. Potts, C., and Wassenhove, L. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters 1, 177-181.
  16. Press, W., Teukolsky, S., Vetterling, W., and Flannery, B. (1992). Numerical Recipes in C : The Art of Scientific Computing, 2nd ed., Cambridge University Press, Cambridge.
  17. Reeves, C. (1997). Genetic Algorithms for the Operations Researcher. INFORMS Journal on Computing 9, 231-250.
  18. Ruiz, R., and Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research 165, 479-494
  19. Szwarc, W. (1993). Single machine total tardiness problem revisited, in Y. Ijiri (ed.). Creative and Innovative Approaches to the Science of Management, Quorum Books, 407-419.
  20. Szwarc, W., Croce, F., and Grosso, A. (1999). Solution of the single machine total tardiness problem. Journal of Scheduling 2, 55- 71.
  21. Tang, L., and Liu, J. (2002). A modified genetic algorithm for the flow shop sequencing problem to minimize mean flow time. Journal of Intelligent Manufacturing 13, 6167.
  22. Vallada, E., Ruiz, R., and Minella, G. (2008). Minimizing total tardiness in the m-machine flowshop problem: a review and evaluation of heuristics and metaheuristics. Computers & Operations Research 35, 1350-1373.
Cytowane przez
Pokaż
ISSN
2299-7075
Język
eng
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu