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

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

Warianty tytułu

EN

The new machine representation of the disjunctive graph for the job shop scheduling problem

• Konferencja: XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych; Zakopane 24-27.09.1998
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

szeregowanie zadań; problem NP-zupełny; graf dysjunkcyjny; macierz grafu

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 1998
• Tom: z. 123
• Strony: 45--54
• Opis fizyczny: Bibliogr. 4 poz., rys.

Twórcy

autor

Błażewicz J.

autor

Pesch E.

autor

Sterna M.

• Instytut Informatyki Politechniki Poznanskiej, 60-965 Poznań, ul. Piotrowo 3a, 061/878-23-66