Problem gniazdowy z ograniczeniem bez czekania. Równoległe algorytmy tabu

• Autorzy: Makuchowski M.

Warianty tytułu

EN

The no-wait job shop problem. Parallel taboo algorithms

• Języki publikacji: PL

Abstrakty

PL

W pracy opisane są równoległe algorytmy poszukiwania z zabronieniami, dedykowane gniazdowemu problemowi z ograniczeniem bez czekania. Proponowane algorytmy zbudowane są z nadrzędnego algorytmu bazującego na wspomnianej technice oraz sterowanego algorytmu konstrukcyjnego. Poszukiwania ograniczone są tylko do rozwiązań możliwych do wygenerowania przez wspomniany algorytm konstrukcyjny. W pracy przedstawia się analizę porównawczą zaproponowanych algorytmów.

EN

This paper deals with parallel tabu search algorithms for a job shop problem with a no-wait constraint and a makespan criterion. The proposed algorithms consist of a master algorithm based on the mentioned technique and slave constructive algorithm. This approach reduces the number of solutions to check only to solutions that can be generated by means of the constructive algorithm. In this paper a comparative analysis of the proposed algorithms is presented.

Słowa kluczowe

PL

problem gniazdowy; problem NP-trudny; algorytm poszukiwania; algorytm konstrukcyjny; algorytm sekwencyjny; algorytm równoległy

EN

no-wait job shop problem; NP-hard; search algorithm; constructive algorithm; sequential algorithm; parallel algorithm

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

Twórcy

autor

Makuchowski M.

• Politechnika Wrocławska,

Bibliografia

• 1. http://www.top500.org/
• 2. Graham R., Lawler E., Lenstra J., Rinnooy Kan A.: Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 1979, 5, 287.
• 3. Makuchowski M.: Problem gniazdowy z ograniczeniem bez czekania. Algorytmy konstrukcyjne. Zeszyty Politechniki Śląskiej (ten numer).
• 4. Nowicki E.: Metoda tabu w problemach szeregowania zadań produkcyjnych. Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław 1999.
• 5. Mascis A., Pacciarelli D.: Job shop scheduling with blocking and no-wait constraints, European Journal of Operational Research. 142(3), 2002, p. 498.
• 6. Framinan J., Schuster C: An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach, Computers and Operations Research 33 (5), 2006, 1200.
• 7. Schuster C: No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems, Mathematical Methods of Operations Research 63 (3), 2006, 473.