Algorytmy szeregowania

---

ISBN 83-87674-39-7
Autor: Czesław Smutnicki
Wydawnictwo: EXIT

---

O książce

Książka adresowana jest do studentów, doktorantów oraz absolwentów specjalizujących się w dziedzinie szeregowania zadań, projektantów systemów zarządzania, planowania i sterowania produkcją jednostkową, krótko- i średnioseryjną, projektantów systemów zrobotyzowanych, a także informatyków zajmujących się implementacją algorytmów komputerowych.

Zagadnienia szeregowania modelują funkcjonowanie rzeczywistych systemów wytwarzania i mogą być stosowane do rozwiązywania praktycznych problemów optymalizacji i sterowania, występujących m.in. w konwencjonalnych i elastycznych systemach wytwórczych, systemach operacyjnych maszyn cyfrowych, systemach wspomagających podejmowanie decyzji, systemach zarządzania.

Książka zawiera przegląd wybranych problemów szeregowania zadań wraz z bogactwem metod i algorytmów stosowanych do ich rozwiązywania, w dużej części projektowanych i badanych przez autora. Wskazuje alternatywne techniki i podejścia polecane dla konkretnych klas problemów praktycznych. Pokazuje przykłady zastosowań, narzędzia programowe i algorytmiczne stosowane w praktyce oraz nowoczesne, zaskakujące swoją budową i efektywnością, metody rozwiązywania. Przedstawiane podejścia mogą być po odpowiedniej modyfikacji stosowane również do analizy wielu złożonych problemów optymalizacji, w tym także dyskretnej i kombinatorycznej, trudnych poprzez brak klasycznych własności analitycznych (różniczkowalność, wypukłość), wieloekstremalność czy też przekleństwo wymiarowości. Osiągnięcia teoretyczne implikują bezpośrednio poprawę jakości komercyjnych pakietów oprogramowania, wspierających działania człowieka w wielu dziedzinach życia.

Uzupełnieniem analiz teoretycznych zawartych w książce są kody źródłowe algorytmów w języku C/C++ wraz z opisem, dostępne w witrynie internetowej autora.

---

Spis treści

1. Wstęp

2. Wprowadzenie

2.1. Rzeczywistość a modelowanie
2.2. Pojęcia podstawowe
2.3. Kryteria optymalizacji
2.4. Związki między kryteriami
2.5. Kryteria optymalizacji a praktyka
2.6. Hierarchia złożoności obliczeniowej
2.7. Charakterystyka rozwiązań
2.8. Regularność kryteriów

3. Struktury systemów sterowania

3.1. Strategia PUSH. Systemy MRP i ERP
3.2. Strategia SQUEZEE. Systemy OPT
3.3. Strategia PULL. Systemy JIT
3.4. Inne strategie: CAW, CRS

4. Aplikacje

4.1. Przemysł chemiczny
4.2. Przemysł samochodowy
4.3. Budownictwo
4.4. Przemysł elektroniczny
4.5. Przemysł ciężki

5. Pakiety programowe

5.1. Systemy do zarządzania projektem
5.2. Systemy szeregowania zadań
5.3. Systemy MRP, MRP II, ERP
5.4. Pakiety symulacyjne

6. Metody optymalizacji dyskretnej

6.1. Metody dokładne
6.2. Metody przybliżone

7. Podstawowe problemy jednomaszynowe

7.1. Problem podstawowy
7.2. Terminy gotowości i zakończenia
7.3. Zadania zależne
7.4. Czasy przygotowania i dostarczenia
7.5. Zadania przerywalne
7.6. Dolne ograniczenia dla problemu ogólnego
7.7. Algorytmy przybliżone problemu ogólnego
7.8. Schematy aproksymacyjne
7.9. Algorytmy przeglądu
7.10. Uwagi

8. Kosztowe problemy jednomaszynowe

8.1. Przypadki wielomianowe
8.2. Model całkowitoliczbowy
8.3. Algorytm PD
8.4. Algorytm B&B
8.5. Podejście dualne
8.6. Alternatywne podejścia dualne
8.7. Proste algorytmy przybliżone
8.8. Algorytmy poszukiwań lokalnych
8.9. Uwagi

9. Złożone problemy jednomaszynowe

9.1. Kary za przyśpieszenia i spóźnienia
9.2. Szeregowanie w systemach JIT

10. Podstawowe problemy przepływowe

10.1. Problem podstawowy
10.2. Przypadki wielomianowe
10.3. Pewne własności problemu
10.4. Schematy B&B
10.5. Podstawowe algorytmy przybliżone
10.6. Algorytm kulturowy
10.7. Algorytmy DS
10.8. Algorytmy TS
10.9. Poszukiwanie mrówkowe
10.10. Symulowane wyżarzanie
10.11. Poszukiwanie ewolucyjne
10.12. Podejście geometryczne
10.13. Podejście sieciowo-neuronowe
10.14. Uwagi

11. Zaawansowane problemy przepływowe

11.1. Kryterium regularne, addytywne
11.2. Modelowanie dodatkowych ograniczeń
11.3. Uwagi

12. Problemy gniazdowe

12.1. Problem i jego modele
12.2. Pewne własności problemu
12.3. Schemat B&B
12.4. Algorytmy priorytetowe
12.5. Algorytmy aproksymacyjne
12.6. Poszukiwania lokalne
12.7. Metoda przesuwanego wąskiego gardła
12.8. Symulowane wyżarzanie
12.9. Poszukiwanie z zakazami
12.10. Spełnianie ograniczeń
12.11. Poszukiwanie ewolucyjne
12.12. Podejście dualne
12.13. Sieci neuronowe
12.14. Uwagi