Krajobraz przestrzeni rozwiązań problemu gniazdowego

• Autorzy: Nowicki, E. , Makuchowski, M.

Warianty tytułu

EN

Landscape of the solution space of the job shop problem

• Języki publikacji: PL

Abstrakty

PL

W pracy bada się krajobraz przestrzeni rozwiązań problemu gniazdowego. Przedstawia się dwa typy ruchów (zamień i wstaw) oraz odpowiadające im miary odległości. Następnie dla różnych instancji problemu gniazdowego testuje się korelacje pomiędzy wartością funkcji celu lokalnego minimum, a jego średnią odległością od wszystkich innych badanych lokalnych minimów (lub odległością do najlepszego minimum lokalnego). Otrzymane rezultaty potwierdzają hipotezę, że zbiór lokalnych minimów ma strukturę "dużej doliny" oraz że jest umiejscowiony w obszarze stanowiącym bardzo niewielką część przestrzeni rozwiązań.

EN

The paper deals with the landscape of the solution space of the job shop problem. Two types of moves (swap and insert) are defined and the resulting distance metrics examined. Next, for instances of the job shop problem, the correlation between the cost of a local minimum and its average distance to all other local minima (as well as its distance to the best-found local minimum) is tested. Obtained results confirm hypothesis that the set of local minima has a "big valley" structure and is confined to a tiny portion of the solution space.

Słowa kluczowe

PL

problem gniazdowy; przestrzeń rozwiązań

EN

job shop problem; solution space

• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2001
• Tom: T. 5, z. 1/2
• Strony: 449-456
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Nowicki, E.

autor

Makuchowski, M.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

Bibliografia

• [1] Aarts Lenstra J.K.: Local search in combinatorial optimization.Chichesster, England, John Wiley and Sons Ltd. 1997
• [2] Boese K., Kahng A., Muddu S.: A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 1994,16,101-113
• [3] Bożejko W., Smutnicki C.: Metody przeszukiwań dyskretnych przestrzeni rozwiązań. Zeszyty Naukowe Politechniki Śląskiej, z. 131,2000,25-35
• [4] Glover F., Laguna M.: Tabu search. Massachusetts USA, Kluwer Academic Publishers 1997
• [5] Manly B.F.J.: Randomization and Monte Carlo Methods in biology. London, Chapman and Hall 1991
• [6] Nowicki E.: Metoda tabu w problemach szeregowania zadań produkcyjnych. Monografia, 27, Oficyna Wydawnicza Politechniki Wrocławskiej 1999
• [7] Nowicki E., Smutnicki C.: A fast tabu search algorithm for the job shop problem. Management Science, 1996,42,797-813
• [8] Nowicki E., Smutnicki C.: A fast tabu search algorithm for the permutation flow shop problem. European Journal of Operation Research, 1996,91,160-175
• [9] Reeves C. R.: Landscapes, operators and heuristic search. Research Report, School of MIS Coventry University (ukaże się w Annals of Operations Research) 1998
• [10] Reeves C.R., Yamada T.: Genetic algorithm, path relinking and the flowshop sequencing problem. Evolutionary Computation, 1998,6,45-6
• [11] Taillard E.: Benchmarks for basic scheduling problems. European Journal of Operational Research, 1993,64,278-285