Parallet algorithm for some single machine scheduling problems

• Autorzy: Bożejko W. , Wodecki M.

Warianty tytułu

PL

Algorytm równoległy dla pewnego jednomaszynowego problemu szeregowania zadań

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: EN

Abstrakty

EN

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.

PL

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

PL

problem jednomaszynowy; szeregowanie zadań; algorytm równoległy

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 81--90
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Bożejko W.

autor

Wodecki M.

• Politechnika Wrocławska, Wrocław