Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Algorytm równoległy dla pewnego jednomaszynowego problemu szeregowania zadań
Konferencja
XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
Języki publikacji
Abstrakty
Problem of scheduling a single machine to minimize total weighted late job can be described as follows: there are n jobs to be processed, each job has an integer processing time, a weight and a due date. The objective is to minimize the total weighted late job, where the late job is performed after its due date. The problem belongs to the class of NP-hard problems. In the paper, we propose sequential and parallel (for SIMD model computing) branch and bound algorithms based on elimination criteria. Finally, the computation results and discussion of the performance of algorithms are presented.
W pracy zajmujemy się problemem optymalizacji kolejności wykonywania zadań na jednej maszynie, w którym kryterium optymalności jest suma kosztów zadań spóźnionych. Jest on oznaczany przez n|1||Sigma wiUi i należy do klasy problemów silnie NP-zupełnych. Przedstawiamy algorytm równoległy (dla modelu SIMD) oparty na metodzie podziału i oszacowań, w którym wykorzystano kryteria eliminacyjne.
Słowa kluczowe
Rocznik
Tom
Strony
81--90
Opis fizyczny
Bibliogr. 10 poz.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0007-0060