Szeregowanie metodą cen dualnych

• Autorzy: Smutnicki C.

Warianty tytułu

EN

Sequencing by dual prices method

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono pewne wyniki badawcze dotyczące zastosowania tzw. podejścia dualnego do rozwiązywania jedno-maszynowego problemu szeregowania z addytywną funkcją celu. Dzięki odpowiedniemu sformułowaniu matematycznemu problemu pierwotnego oraz pewnym jego własnościom, możliwe jest także efektywne rozwiązanie problemu dualnego. Podejście to prowadzi do dwupoziomowej procedury optymalizacyjnej ze specjalizowaną dyskretną wersją metody programowania dynamicznego na dolnym poziomie oraz procedurą poszukiwania maksimum funkcji wielu zmiennych na poziomie górnym. Przedstawiono pewne własności problemów, przedyskutowano złożoność obliczeniowej odpowiednich algorytmów, zanalizowano przydatność techniki sub-gradientowej do rozwiązania problemu górnego poziomu oraz podano ilustracyjne wyniki badań numerycznych. W wyniku zastosowania proponowanej metody możemy uzyskać: (a) dolne ograniczenie wartości funkcji celu (możliwe do wykorzystania w metodzie dokładnej, np. B&B), (b) rozwiązanie optymalne (przy spełnieniu pewnych dodatkowych warunków), (c) rozwiązanie przybliżone. Otrzymane wnioski badawcze mogą być zastosowane bezpośrednio przy modelowaniu i rozwiązywaniu bardziej złożonych zagadnień szeregowania, takich jak np. problem gniazdowy z addytywną funkcją celu.

EN

In this paper there are presented some results of the dual approach used in order to solve a single-machine scheduling problem with the additive goal function. Due to proper mathematical formulation of the primal problem and some its properties, the dual problem can be solved in an efficient way. The approach leads to two-level optimisation procedure with specialised discrete version of dynamic programming method on the lower level and a procedure of seeking maximum of multiple-variable function on the upper level. Some properties of problems there are presented, computational complexities of algorithms are discussed, application of sub-gradient technique to solve the upper level problem is analysed and some illustrative numerical examples are also given. The proposed method can provide: (a) lower bound of the optimal goal function value (for the use in an exact method, e.g. B&B), (b) optimal solution (if only some auxiliary condition hold), (c) approximate solution. Obtained research results can be applied immediately in modelling and solving more complex scheduling problems, as an example the job-shop problem with additive goal function.

Słowa kluczowe

PL

szeregowanie zadań; metoda cen dualnych

EN

scheduling problem; dual prices method

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 1999
• Tom: T. 3, z. 1
• Strony: 309--318
• Opis fizyczny: Bibliogr. 4 poz., rys.

Twórcy

autor

Smutnicki C.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska