Nowe wykorzystanie metody blokowej w konstrukcji algorytmów heurystycznych dla ogólnego problemu przepływowego

• Autorzy: Grabowski J. , Pempera J.

Warianty tytułu

EN

New concept of using block method in the construction local search heuristics for the general flowshop problem

• Języki publikacji: PL

Abstrakty

PL

Własności blokowe są z powodzeniem stosowane do usuwania ruchów nierokujących poprawy dla wielu otoczeń stosowanych w algorytmach popraw dla problemów szeregowania. W pracy, dla ogólnego problemu przepływowego, zaproponowano nowy sposób przeglądania otoczenia, który pozwala na eliminację znacznie większego zbioru ruchów. W celu sprawdzenia efektywności metody przeprowadzono eksperyment komputerowy na instancjach Taillarda.

EN

The block properties are successfully applied to a priory eliminate non promising moves from the neighborhood for many local search algorithm of solving scheduling problems. In this paper, for the general flowshop problem, it presents new method of searching the neighborhood, which gives rise to eliminate highly greater set of moves. To validate efficiency of the proposed method, computational experiment have been executed on a well-known Taillard's benchmarks.

Słowa kluczowe

PL

algorytm heurystyczny; metoda blokowa; problem szeregowania; problem przepływowy; instancje Taillarda

EN

heuristic algorithm; block method; scheduling problem; flowshop problem; Taillard's benchmarks

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2008
• Tom: z. 150
• Strony: 45--50
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Grabowski J.

autor

Pempera J.

• Politechnika Wrocławska,

Bibliografia

• 1. Gupta J.N.D., Stafford S.: Flowshop scheduling research after five decades. European Journal of Operational Research, 169, 2006, s. 699-711.
• 2. Johnson S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 1954, s. 61-68.
• 3. Garey M.R., Johnson D.S., Sethi R.: The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1, 1976, s. 117-129.
• 4. Grabowski J., Nowicki E., Smutnicki C.: Metoda blokowa w zagadnieniach szeregowania zadań. EXIT, Warszawa 2003.
• 5. Low C, Liang Z.: Determining optimal combination of genetic operators for flow shop scheduling problem. International Journal of Advanced Manufacturing Technology, 30, 2006, 302-308.
• 6. Low C, Yeh J.Y., Huang K.I.: A robust simulated annealing heuristic for flow shop scheduling problem. International Journal of Advanced Manufacturing Technology, 23, 2004, 762-767.
• 7. Nowicki E., Smutnicki C.: A fast taboo search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 106, 1998, s. 226-253.
• 8. Grabowski J., Pempera J.: New block properties for the permutation flow-shop problem with application in TS. Journal of the Operational Research Society 26 2001, s. 210-220.
• 9. Grabowski J., Wodecki M.: A very fast tabu search algorithm for the permutation flow shop problem with makespan criterium. Computers and Operations Research 31, 2004, s. 1891-1909.
• 10. Solimanpur M., Vrat P., Shankar R.: A neuro-tabu search heuristic for the flow shop scheduling problem. Computers and Operations Research 31, 2004, s 2151-2164.
• 11. Ying K.C., Liao C.J. (2004). An ant colony system for permutation flow-shop sequencing. Computers and Operations Research 31, 2004, s. 762-767.
• 12. Tandon M., Cummings P.T. Levan M.D.: Flowshop sequencing with non-permutation schedules. Computers and Chemical Engineering. 15, 1991, s. 601-607.
• 13. Taillard E.: Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 1993, s. 278-285.
• 14. Nawaz E., Enscore E.E., Ham I.: A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega International Journal of Management Science, 11, 1993, s. 91-95.