PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 31 | 271--280
Tytuł artykułu

Heurystyczna procedura szeregowania zadań w systemie maszyn równoległych przy ograniczonej dostępności zasobów

Treść / Zawartość
Warianty tytułu
Heuristic Procedure of Task Scheduling in Parallel Machine System with Limited Resource Access
Języki publikacji
PL
Abstrakty
Celem artykułu jest prezentacja rezultatów badan problemu czasowo-optymalnego szeregowania zadań i rozdziału zasobów w systemie maszyn równoległych. System ten posiada m równoległych maszyn, na których należy wykonać n zadań. Zakładamy, że wszystkie zadania są niezależne i liczba zadań jest większa od liczby maszyn. Zakładamy ponadto, że występuje stałość przydziału zasobów do maszyn podczas wykonywania całego zbioru zadań. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny problemu. Ponieważ problem ten należy do klasy problemów NP-zupełnych zaproponowano pewien algorytm heurystyczny dla rozwiązania postawionego problemu. Zaprezentowano rezultaty eksperymentów obliczeniowych wykonanych na bazie podanego w pracy algorytmu heurystycznego.(abstrakt oryginalny)
EN
The aim of the paper is to present results of research on the problem of time- optimal tasks scheduling and resources allocation in parallel machines system. We consider system having m parallel machines. This system can execute n tasks. We assume that all n tasks are independent and number of tasks is greater than number of machines. We also assume that is constancy of resources allocation in execution time all tasks set. For some tasks processing time function the mathematical model of this problem is formulated. Because our problem belongs to the class of NP-complete problems we propose an heuristic algorithm for solution of this problem. Some results of executed numerical experiments for basis of proposed heuristic algorithm are presented. (original abstract)
Rocznik
Tom
31
Strony
271--280
Opis fizyczny
Twórcy
  • Politechnika Wrocławska
Bibliografia
  • [1]Bianco L.i in., Preemptive scheduling of multiprocessor tasks on the dedicated processors system subject to minimal lateness. Information Processing Letters, 46, 1993, pp. 109-113.
  • [2]Bianco L. i in., Linear algorithms for preemtive scheduling of multiprocessor tasks subject to minimal lateness. Discrete Applied Mathematics, 72, 1997, pp. 25-46.
  • [3]Błażewicz J. i in., Badania operacyjne dla informatyków, WNT, Warszawa 1983.
  • [4]Błażewicz J. i in., Scheduling independent multiprocessor tasks before deadlines. Discrete Applied Mathematics 65 (1-3), 1996, pp. 81-96.
  • [5]Błażewicz J. i in., Scheduling in Computer and Manufacturing Systems. Springer-Verlag, Berlin-Heidelberg, 1993.
  • [6]Błażewicz J., Liu Z., Scheduling multiprocessor tasks with chain constraints. European Journal of Operational Research, 94, 1996, pp. 231-241.
  • [7]Boctor F. F., A new and efficient heuristic for scheduling projects will resources restrictions and multiple execution model. European Journal of Operational Research, vol. 90, 1996, pp. 349-361.
  • [8]Brah S.A., Loo L.L., Heuristics for scheduling in a flow shop with multiple processors, European Journal of Operational Research, Vol. 113, No. 1, 1999, pp. 113-122.
  • [9]Buchalski Z., Szeregowanie zadań na różnych maszynach równoległych z razdziałem ograniczonych zasobów. Zeszyty Naukowe Politechniki Śląskiej, Automatyka, No. 1389, Gli- wice, 1998, pp. 77-84.
  • [10]Buchalski Z., A Program Scheduling Heuristic Algorithm in Multiprocessing Computer System with Limited Memory Pages. Polish Journal of Environmental Studies, Vol. 15, No. 4C, 2006, pp. 26-29.
  • [11]Buchalski Z., Minimising the Total Processing Time for the Tasks Scheduling on the Parallel Machines System. Proc. of the 12th IEEE International Conference on Methods and Models in Automation and Robotics, Domek S., Kaszyński R. (Eds.), Międzyzdroje, Poland, MMAR 2006, 28-31 August 2006, pp. 1081-1084.
  • [12]Cheng J., Karuno Y., Kise H., A shifting bottleneck approach for a parallel-machine flowshop scheduling problem, Journal of the Operational Reasearch Society of Japan, Vol. 44, No. 2, 2001, pp. 140-156.
  • [13]Gupta J.N.D., Hariri A.M.A., Potts C.N., Scheduling a two-stage hybrid flow shop with parallel machines at the first stage, Annals of Operations Research, Vol. 69, No. 0, 1997, pp. 171-191.
  • [14]Hoogeveen J.A., Lenstra J.K., Veltman B., Preemptive scheduling in a two-stage multiprocessor flow shop in NP-hard, European Journal of Operational Research, Vol. 89, No.1, 1996, pp. 172-175.
  • [15] Janiak A., Kovalyov M., Single machine scheduling subject to deadlines and resources dependent processing times. European Journal of Operational Research, vol. 94, 1996, pp. 284-291.
  • [16]Józefowska J. i in., Discrete-continuous scheduling to minimize maximum lateness, Pro- ceedings of the Fourth International Symposium on Methods and Models in Automation and Robotics MMAR'97, Międzyzdroje, Poland, 1997, pp. 947-952.
  • [17]Józefowska J. i in., Local search metaheuristics for discrete-continuous scheduling problems, European Journal of Operational Research, 107, 1998, pp. 354-370.
  • [18]Józefowska J., Węglarz J., Discrete-continous scheduling problems - mean completion time result, European Journal of Operational Research, vol. 94, No. 2, 1996, pp. 302-310.
  • [19]Józefowska J., Węglarz J., On a methodology for discrete-continous scheduling, European Journal of Operational Research, Vol. 107, No. 2, 1998, pp. 338-353.
  • [20]Ng C.T. i in., Group Scheduling with controllable setup and processing times: minimizing total weighted completion time, Ann. Oper. Res., 133, 2005, pp. 163-174.
  • [21]Nowicki E., Smutnicki C., The flow shop with parallel machines. A Tabu search approach. European Journal of Operational Research, 106, 1998, pp. 226-253.
  • [22]Santos D.L., J.L., Deal D.E., An evaluation of sequencing heuristics in flow shops with multiple processors, Computers and Industrial Engineering, Vol. 30, No. 4, 1996, pp. 681-691.
  • [23]Węglarz J., Multiprocessor scheduling with memory allocation - a deterministic approach. IEEE Trans. Comput., C-29, 1980, pp. 703-710.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171542764

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.