Metaheurystyki w szeregowaniu zadań uwarunkowanych czasowo

• Autorzy: Ocetkiewicz K.M.

Warianty tytułu

EN

Metaheuristics in scheduling deteriorating jobs

• Języki publikacji: PL

Abstrakty

PL

W artykule tym zbadano zastosowanie algorytmów metaheurystycznych w problemach szeregowania zadań uwarunkowanych czasowo. Porównano wyniki algorytmu genetycznego, ewolucji różnicowej oraz symulowanego wyżarzania, z reprezentacjami rozwiązania: permutacyjną, opartą o priorytety reguł i kodowaniem przedziałowym, osiągnięte w rozwiązywaniu NP-trudnego problemu 1 | Pi = ai + bisi | [suma]WiCi, Gdzie to możliwe, wyniki porównano z rozwiązaniami optymalnymi.

EN

This article investigates the usefulness of metaheuristics in scheduling deteriorating jobs. Results in solving the NP-hard problem 1 | Pi = ai + bisi | ?WiCi of genetic algorithm, differential evolution and simulated annealing for the following representations of solution: permutation-based encoding, priority rule-based encoding and subrange encoding were compared. Where applicable, results were also compared to the optimal solutions.

Słowa kluczowe

PL

metaheurystyki; zadania uwarunkowane czasowo

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2008
• Tom: T. 16
• Strony: 391--396
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Ocetkiewicz K.M.

• Politechnika Gdańska, Katedra Algorytmów i Modelowania Systemów

Bibliografia

• [1] Cheng T.C.E, Ding Q., Lin B.M.T.: A concise survey of scheduling with time-dependent processing limes, W: European Journal of Operational Research 152, s.: 1-13, 2004.
• [2] Storn R., Price K: A simple and Efficient Heuristic for Global Optimization Over continuous Spaces. W: Journal of Global Optimization 11, s. 241-354, 1997.
• [3] Nearchou AC., Omirou S.L.: Differential evolution for sequencing and scheduling optimization. W: Journal of Heuristics 12, s. 395-411, 2006.
• [4] Onwubolu G., Davendra D.: Scheduling flow shops using differential evolution algorithm. W: European Journal of Operational Research 171, s. 674-692, 2006.
• [5] Cerny V.: A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. W: Journal of Optimization Theory and Applications 45, s. 41-51, 1985.
• [6] Kirkpatrick S., Gelatt C.D., Vecchi M.P.: Optimization by Simulated Annealing. W: Science 4598, s. 671-680, 1983.
• [7] Cheng R., Gen M., Tsujimura Y.: A tutorial survey of job-shop scheduling problems using genetic algorithms - I. Representation. W: Computers & Industrial Engineering 30, s.983-997, 1996.
• [8] Bachman A, Janiak A, Kovalyov M.Y.: Minimizing the total weighted completion time of deteriorating jobs. W: Information Processing Letters 81, s. 81-84, 2002.