Algorytm blokowy szeregowania operacji w systemie gniazdowym

• Autorzy: Józef Grabowski , Eugeniusz Nowicki , Czesław Smutnicki

Warianty tytułu

Job - Shop Problem

• Języki publikacji: PL

Abstrakty

W artykule rozważany jest jeden z najbardziej ogólnych i najtrudniejszych problemów harmonogramowania, tzw. problem warsztatowy. Problem jest dominujący w rzeczywistych systemach produkcyjnych. W artykule przedstawiono problem job-shop z funkcją celu typu C_max, a następnie - równoważnie sformułowany w języku teorii grafów. Następnie definiuje się blok zadań na ścieżce krytycznej, a właściwości eliminacyjne bloku są udowadniane w podstawowym twierdzeniu. Podana jest również procedura budowy drzewa rozwiązania, generowanego przez algorytm oparty na metodzie branch-and-bound. Poza tym pokazano zbieżność algorytmu. W końcowej części pracy przedstawiono różne postacie dolnych granic oraz omówiono programową implementację algorytmu i wyniki badań.

EN

In the paper, there is considered one of the most general and difficult scheduling problems, so called: job-shop problem. The problem is the predominant one in real production systems. In the paper the job-shop problem with the C_max - type objective function is presented and next - equivalently formulated in the graph theory language. Then, the job block on the critical path is defined and elimination properties of the block are proved in a fundamental theorem. There is also given a procedure of construction of a solution tree, generated by an algorithm based on the branch-and-bound method. Besides, the convergence of the algorithm is shown. In the final part of the paper, various forms of the lower bounds are presented and the program implementation of the algorithm as well as testing results are discussed.(original abstract)

Słowa kluczowe

PL

Harmonogram; Algorytmy; Teoria szeregowania zadań

EN

Schedule; Algorithms; Task scheduling theory

• Czasopismo: Przegląd Statystyczny
• Rocznik: 1988
• Tom: 35
• Numer: z. 1
• Strony: 67--80

Twórcy

autor

Józef Grabowski

autor

Eugeniusz Nowicki

autor

Czesław Smutnicki

Bibliografia

• Adrabiński A., Algorytmy szeregowania operacji w dyskretnych systemach produkcyjnych z maszynami równoległymi, Praca doktorska, Raport serii Preprinty, nr 32/83, Instytut Cybernetyki Technicznej Politechnika Wrocławska, Wrocław 1983.
• Balas E., Machine Sequencing via Disjunctive Graphs an Implicit Enumeration Algorithm, Operations Research 17 (1969), s. 941 - 957.
• Bouma P. W., Job-Shop Scheduling: A Comparison of Three Enumeration Schemas in a Branch-and-Bound Approach, Master thesis, Erasmus University Rotterdam, Faculty of Economics, Departament of Econometries and Operations Research, Rotterdam 1982.
• Carlier J., Problems d'ordonnancement a contraintes de resources. Algorithms et complexité, Methodologie and architecture les systèmes informatiques, N-40, Université P. et M. Curie, Paris 1984.
• Grabowski J., Uogólnione zagadnienia optymalizacji kolejności operacji w dyskretnych systemach produkcyjnych, Prace naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej nr 9, Wydawnictwo Politechniki Wrocławskiej, Wrocław 1979.
• Grabowski J., Nowicki E., Smutnicki Cz., Nowe metody wyznaczania dolnych ograniczeń dla zagadnienia kolejnościowego gniazdowego, Zeszyty Naukowe Akademii Górniczo-Hutniczej, Automatyka 39 (1985).
• Grabowski J., Nowicki E., Smutnicki Cz., Metoda blokowa w gniazdowych zagadnieniach kolejnościowych, Zeszyty Naukowe Politechniki Śląskiej, Automatyka 84 (1986).
• Grabowski J., Nowicki E., Zdrzałka S., A block approach for single-machine scheduling with release dates and due dates, European Journal of Operational Research 26 (1986), s. 278 - 285.
• Grabowski J., Skubalska E., Smutnicki Cz., On flow-shop with release and due dates to minimize maximum lataness, Journal of the Operational Research Society 34 (1983), s. 615 - 620.
• Graham E., Lawler J. K., Lenstra A. H. G., Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics 5 (1979), s. 287 - 326.
• Lenstra J. K., Sequencing by Enumerative Methods, Mathematical Centre Track 69, Mathematish Centrum, Amsterdam 1973.
• Nowicki E., Smutnicki Cz., On lower bounds on the minimum maximum lataness on one machine subject to release date, Operations Research 24 (1987), s. 106- 110.
• Rinnooy Kan, A. H. G., Machine Scheduling Problems Classification, Complexity and Computations, Nijhoff, The Hague 1976.