Metoda blokowa w zagadnieniach szeregowania zadań

---

ISBN 83-87674-49-4
Autor: Józef Grabowski, Eugeniusz Nowicki, Czesław Smutnicki
Wydawnictwo: EXIT

---

O książce

Książka dotyczy problematyki szeregowania zadań. Problematyka ta występuje zarówno w systemach produkcyjnych, jak i w systemach i sieciach komputerowych. W książce przedstawia się modele matematyczne problemów, ich własności oraz algorytmy, oparte przede wszystkim na tzw. metodzie blokowej. Metoda ta jest oryginalnym podejściem w teorii szeregowania zadań, które korzystając z prostego pojęciowo i strukturalnie modelu grafowego, własności ścieżki krytycznej w grafie oraz pewnych innych stukturalnych własności problemów, pozwala projektować algorytmy dokładne i przybliżone o zaskakująco dobrych własnościach numerycznych. Prezentowana książka jest pierwszym w języku polskim tak obszernym i w miarę wyczerpującym przedstawieniem metody blokowej będącej dorobkiem własnym autorów. Po wprowadzeniu czytelnika w problematykę szeregowania zadań (notacja, kryteria, złożoność obliczeniowa) omawia się szczegółowo trzy najbardziej podstawowe typy problemów szeregowania: problemy jednomaszynowe, problemy przepływowe oraz problemy gniazdowe. Przedstawia się także szereg uogólnień praktycznych, takich jak: transport, przezbrojenia, buforowanie, ograniczona pojemność systemu, paletyzacja. Duża liczba przykładów ilustracyjnych powoduje, że lektura książki jest stosunkowo łatwa, mimo jej dość teoretycznego charakteru.

Książka jest adresowana dla studentów starszych lat kierunków Automatyka i Robotyka oraz Informatyka, doktorantów, jak i do pracowników naukowych. Może być ona także pomocna dla menedżerów planistów i projektantów w zakresie krótkoterminowego zarządzania i planowania produkcji.

---

Spis treści

1. Wstęp

I. Wprowadzenie

2. Dane, ograniczenia i kryteria

2.1. Pojęcia podstawowe
2.2. Równoważność kryteriów

3. Problemy

3.1. Klasyfikacja zagadnień

II. Złożoność obliczeniowa i metody rozwiązywania zagadnień programowania dyskretnego

4. Złożoność obliczeniowa

4.1. Miary złożoności obliczeniowej
4.2. Zagadnienia klasy P i NP, redukowalność
4.3. Przykładowe zagadnienia NP-zupełne

5. Metody rozwiązywania zagadnień programowania dyskretnego

5.1. Bezpośrednie metody obliczeniowe
5.2. Metody lokalnej optymalizacji
5.3. Wnioski i uwagi

III. Problemy jednomaszynowe

6. Problemy "1BC" i "1BL"

6.1. Problem wyjściowy
6.2. Gotowość, dostarczenie, pilność zadań
6.3. Zależność zadań
6.4. Problem wąskiego gardła
6.5. Przerywalność zadań
6.6. Metody rozwiązywania
6.7. Dolne ograniczenia
6.8. Algorytmy aproksymacyjne
6.9. Algorytm C
6.10. Algorytm blokowy GNZ

7. Problemy "1Bf"

7.1. Problemy wielomianowe
7.2. Przerywalność zadań
7.3. Pewne własności problemu
7.4. Dolne ograniczenia
7.5. Algorytmy przybliżone
7.6. Algorytm blokowy ZG

8. Problemy "1Bh"

8.1. Kary za przyspieszenia i spóźnienia
8.2. Dwupoziomowa dekompozycja

IV. Problemy przepływowe

9. Podstawowe własności. Algorytmy dokładne

9.1. Ogólne sformułowania zagadnienia
9.2. Dwumaszynowe zagadnienie przepływowe
9.3. Trójmaszynowe zagadnienie przepływowe
9.4. Pewne własności zagadnienia
9.5. Blokowa metoda podziału i ograniczeń
9.6. Zasady wyboru zadań do przesuwania
9.7. Metody wyznaczania dolnych ograniczeń
9.8. Algorytm
9.9. Wnioski i uwagi
9.10. Implementacja algorytmu
9.11. Przykład obliczeniowy
9.12. Zagadnienie przepływowe

10. Algorytmy przybliżone

10.1. Algorytmy priorytetowe
10.2. Algorytmy oparte na metodzie redukcji liczby maszyn
10.3. Algorytmy oparte na metodzie relaksacji możliwości wykonawczych maszyn
10.4. Algorytmy oparte na metodzie wstawień

V. Problemy gniazdowe

11. Metoda blokowa w klasycznych problemach gniazdowych

11.1. Model matematyczny
11.2. Bloki operacji i ich własności
11.3. Blokowa metoda podziału i ograniczeń
11.4. Przegląd metod podziału i ograniczeń

12. Metoda blokowa w problemach gniazdowych z maszynami równoległymi

12.1. Model matematyczny
12.2. Eliminacyjne własności bloków operacji
12.3. Blokowa metoda podziału i ograniczeń
12.4. Podsumowanie

13. Algorytmy konstrukcyjne w problemach gniazdowych

13.1. Klasyczny problem gniazdowy
13.2. Problem gniazdowy z maszynami równoległymi

14. Uogólnienia problemów gniazdowych

14.1. Przezbrojenia i transport
14.2. Palety
14.3. Inne uogólnienia

Epilog

Literatura