Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Zeszyty Naukowe. Automatyka / Politechnika Śląska

2 1998

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: macierz grafu

Sortuj według:

Ogranicz wyniki do:

Szeregowanie zadań w systemach z ograniczoną dostępnością maszyn

Błażewicz J., Drozdowski M., Formanowicz P., Kubiak W.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

1998

z. 123

55-63

W pracy przedstawiono wybrane problemy szeregowania zadań na maszynach z okresami niedostępności. Rozważane są zagadnienia dotyczące maszyn równoległych identycznych i dowolnych, a także przepływowego systemu obsługi. W przypadku maszyn równoległych omawiane problemy dotyczą zadań podzielnych bez ograniczeń kolejnościowych oraz z takimi ograniczeniami i kryterium Cmax oraz Lmax. Przedstawione są wyniki dotyczące złożoności obliczeniowej oraz algorytmy oparte na programowaniu liniowym. Dla problemów szeregowania w przepływowym systemie obsługi określono złożoność obliczeniową problemu szeregowania na dwóch maszynach z kryterium Cmax. Ponadto przedstawiono własność tego problemu przydatną przy konstrukcji algorytmu podziału i ograniczeń oraz wyniki eksperymentu obliczeniowego.

The selected problems of scheduling tasks on machines with a limited availability are presented. Problems concerning parallel identical and unrelated machines and flow shop system are considered. In the case of parallel machines the problems presented are concerned with preemptive tasks with and without precedence constraints and Cmax and Lmax criteria. Computational complexity results and algorithms based on linear programming are presented. In the case of flow shop the computational complesity for two-machine problem with Cmax criterion is analysed. Moreover, a property of this problem is presented which is useful for constructing a branch and bound algorithm, and results of computational experiment are presented.

Nowa reprezentacja maszynowa grafu dysjunkcyjnego dla problemu szeregowania w ogólnym systemie obsługi

Błażewicz J., Pesch E., Sterna M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

1998

z. 123

45-54

W pracy przedstawiono nową reprezentację maszynową grafu dysjunkcyjnego dla problemu szeregowania w ogólnym systemie obsługi - macierz grafu, charakteryzującą się korzystną złożonością pamięciową i wysoką efektywnością czasową procedur ją obsługujących. Łączy ona zalety trzech klasycznych reprezentacji struktur grafowych: macierzy sąsiedztwa, listy poprzedników i listy następników, umożliwiając łatwy dostęp do różnego rodzaju informacji opisujących operacje w ogólnym systemie obsługi.

This paper is concerned with a new time and memory efficient representation of the disjunctive graph - the graph matrix, used for describing instances of the job shop scheduling problem. The proposed data structure combines advantages of the classical graph representations like a neighborhood matrix and predecessors' and successors' lists delivering combined information on a job shop and enabling easy manipulation of the problem data.