Harmonogramowanie przedsięwzięć budowlanych za pomocą problemu przepływowego ze specyficznymi czasami transportu

• Autorzy: Bożejko W. , Hejducki Z. , Podolski M. , Uchroński M.

Warianty tytułu

EN

Scheduling of construction projects by using the flow shop problem with specific transport times

• Konferencja: XVI Krajowa Konferencja Automatyzacji Procesów Dyskretnych, (2008, Gliwice, Polska)
• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrujemy permutacyjny problem przepływowy będący jednym z najtrudniejszych problemów kombinatorycznych. Dla zamodelowa-nia specyficznych własności pojawiających się w praktycznych problemach harmonogramowania przedsięwzięć budowlanych zastosowaliśmy czasy transportu o ujemnej wartości. Przedstawiamy algorytm jego rozwiązywania oparty na metodzie tabu search.Wykonano wiele obliczeń dla trudnych przykładów o dużych rozmiarach zamieszczonych w pracy Taillard [14]. Otrzymane wyniki obliczeniowe porównano z powszechnie obecnie stosowanym algorytmem konstrukcyjnym NEH ([13]), wynikami dokładnego algorytmu B&B oraz najlepszymi znanymi w literaturze rozwiązaniami.

EN

In this paper we consider a permutational flow shop problem which is one of the difficult combinatorial problems. A negative times of transports have been using to model a specific constraints of the problem. We propose a tabu search approach. Tests were done for a Taillard [14] benchmarks. Obtained results were compared to constructive algorithm NEH ([13]), exact B&B algorithm and the best known results from literature.

Słowa kluczowe

PL

permutacyjny problem przepływowy; NEH; B&B; harmonogramowanie; tabu

EN

permutation flow shop problem; NEH; B&B; schedule; tabu

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2008
• Tom: z. 151
• Strony: 93--102
• Opis fizyczny: bibliogr. 16 poz.

Twórcy

autor

Bożejko W.

autor

Hejducki Z.

autor

Podolski M.

autor

Uchroński M.

• Politechnika Wrocławska; Wydział Elektroniki; Instytut Informatyki, Automatyki i Robotyki ul. Z. Janiszewskiego 11/17, Wrocław Tel: [phone],

Bibliografia

• Adenso-Diaz B.: Restricted neightborthood in the tabu search for the flowshop problem. European Journal of Operational Research 62, 1992, 27-37.
• Biruk S., Jaworski K. M., Tokarski Z.: Podstawy organizacji robót budowlanych. Wydawnictwo Naukowe PWN, Warszawa 2007.
• Glover F: Tabu Search. Part I, ORSA Journal of Computing 1, 1989, 190-206.
• Glover F: Tabu Search. Part II, ORSA Journal of Computing 2, 1990, 4-32.
• Glover F, Laguna M.: Tabu Search. Kluwer Academic Publishers, Massachusetts USA, 1997.
• Grabowski J., Pempera J.: New block properties for the permutation flow-shop problem with aplication in TS. Journal of the Operational Research Society 52, 2001,210-222.
• Grabowski J., Wodecki M.: A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers & Operations Research 31, 2004, 1891-1909.
• Gupta J. N. D., Stafford Jr E. F: Flowshop scheduling research after five decades. European Journal of Operational Research 169, 2006, 699-711.
• Hurnik J.: Makespan minimization for flow-shop problem with transportation times and a single robot, Discrete Applied Mathematics 112, 2001, 199-216.
• Nowicki E.: Metoda tabu w problemach szeregowania zadań produkcyjnych. Prace Naukowe ICT PWr, Seria Monografie, 1999.
• Nowicki E., Smutnicki C: A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research 91, 1996, 160-175.
• Smutnicki C: Algorytmy szeregowania. Akademicka Oficyna Wydawnicza EXIT, Warszawa 2002.
• Taillard E.: Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research 47, 1990, 65-74.
• Taillard E.: Benchmarks for Basic scheduling problems. European Journal of Operational Research 64, 1993,278-285.
• Widmer M., Hertz A.: A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research 41, 1989, 186-193.
• http://www2.lifl.fr/ talbi/challenge2007