Heurystyczny algorytm szeregowania zadań w systemie maszyn równoległych z równoczesnym rozdziałem zasobów

• Autorzy: Buchalski, Z.

Warianty tytułu

EN

An heuristic algorithm for the tasks scheduling on parallel machines system with simultaneous resources allocation

• Języki publikacji: PL

Abstrakty

PL

Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki eksperymentów obliczeniowych wykonanych na bazie zaproponowanego algorytmu heurystycznego.

EN

In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resources to m parallel machines is considered. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of executed numerical experiment for basis of proposed heuristic algorithm are presented.

Słowa kluczowe

PL

dyskretny system produkcyjny; szeregowanie zadań; algorytmy heurystyczne

EN

discrete productive system; tasks scheduling; heuristic algorithms

• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2005
• Tom: T. 9, z. 1-2
• Strony: 37-45
• Opis fizyczny: Bibliogr. 13 poz., tab.

Twórcy

autor

Buchalski, Z.

• Instytut Cybernetyki Technicznej Politechniki Wrocławskiej

Bibliografia

• [1] Błażewicz J., Dell' Olmo P., Drozdowski M., Speranza M. G .: Scheduling multiprocessor tasks on three dedicated processors. Information Processing Letters, 41, 1992, 275–280
• [2] Błażewicz J., Drabowski M., Węglarz J.: Scheduling multiprocessor tasks to minimize schedule length. I EEE Transactions on Computers C–35, 1986, 389–393
• [3] Boctor F . F .: A new and efficient heuristic for scheduling projects will resources restrictions and multiple execution models. European Journal of Operational Research, vol. 90, 1996, 349–361
• [4] Ishii H., Martel C., Masuda T., Nishida T.: A generalized uniform processor system . Oper. Res., vol. 33, 1985, 346–362
• [5] Janiak A.: Single machine scheduling problem with a common deadline and resource dependent release dates. European Journal of Operational Research, vol. 53, 1991, 317–325
• [6] Buchalski Z.: Optimization of programs scheduling and primary memory allocation in multiprocessing computer systems. Information Systems Architecture and Technology I S AT ’ 98, Wrocław, 1998, 246–253
• [7] Bachman A., Janiak A.: Jednomaszynowy problem szeregowania zadań czasowo i zasobowo zależnych przy kryterium minimalizacji czasu zakończenia wykonywania zadań. Zeszyty Naukowe Politechniki ŒŚląskiej Nr 1474, seria – Automatyka, Gliwice, z. 129, 2000, 23–32
• [8] Bianco L., Błażewicz J., Dell' ’ Olmo P., Drozdowski M.: Preemptive multiprocessors task scheduling with release times and times windows. Annals of Operations Research, 70, 1997, 43–55
• [9] Buchalski Z.: Szeregowanie zadań w systemach wielomaszynowych z czasem realizacji zależnym od ilości zasobów . Zeszyty Naukowe Politechniki Śląskiej, Nr 1474, seria – Automatyka, Gliwice, z. 129, 2000, 33-39
• [10] Janiak A., Kovalyov M.: Single machine scheduling subject to deadlines and resources dependent processing times. European Journal of Operational Research, vol. 94, 1996, 284–291
• [11] Józefowska J., Węglarz J.: On a methodology for discrete-continuous scheduling. European Journal of Operational Research, vol. 107, 1998, 338–353
• [12] Józefowska J., Mika M., Różycki R., Waligóra G ., Węglarz J.: Rozwi¹zywanie dyskretno-ciągłych problemów rozdziału zasobów przez dyskretyzację zasobu ciągłego. Zeszyty Naukowe Politechniki Śląskiej, Nr 1474, seria – Automatyka, Gliwice, z. 129, 2000, 221–229
• [13] Nowicki E ., Smutnicki C.: The flow shop with parallel machines. A tabu search approach . European Journal of Operational Research, 106, 1998, 226–253