Sposób szeregowania zadań dla jednej maszyny o ograniczonych zasobach

• Autorzy: Cechowicz R.

Warianty tytułu

EN

Single machine scheduling with constrains

• Języki publikacji: PL

Abstrakty

PL

W artykule opisano system szeregowania zadań niepodzielnych na jednej maszynie. System pozwala zoptymalizować plan produkcji poprzez ograniczenie ilości operacji transportowych i pomocniczych oraz poprzez poszukiwanie takiej kolejności realizacji zadań, dla której łączny czas wykonania będzie możliwie najmniejszy. Zastosowano zmodyfikowany algorytm genetyczny pozwalający na częściowe dostrojenie procesu do struktury danych. Testy przeprowadzone zarówno na danych dostępnych publicznie, jak i na danych pochodzących ze środowiska wytwórczego udowodniły skuteczność przyjętych rozwiązań.

EN

A system for scheduling indivisible tasks on a single, periodically accessible machine is presented in this paper. Because of the constrains existing in the environment, the scheduling problem presented here is similar to the one-dimensional bin-packing. The tasks, stacked on a palettes (Fig.1), were transported to the machine. The palette caould be replaced by another one only after completing all the tasks assigned to it. Each task was defined by an execution time Tz and an auxiliary time Tp. The transportation time To was added to the last task from each palette and to the last task executed within the machine availability period Tm (Fig.2). A modified genetic algorithm was used for the scheduling, where the parameter K defined the number of gene changeovers (representing changing the sequence of palettes and changing the sequence of tasks within a palette) during one mutation. The results obtained for the data available in public [13] and in selected publications are presented in Tab.1. It was noted that the distribution of scheduling results (fitness=Cmax) could be modified by changing the parameter K (Figs.4 and 6). The observation was proved statistically for the data from the manufacturing system by means of the median test run for the set of 500 results, 50 for each K=1..10 (χ2=19, df=9, p=0,0254<0,05). The results of the test proved that the scheduling algorithm could be tuned for speed by adjusting the value of K. Assuming that the process was random, it could be calculated that for K=5 the expected time of getting the solution Cmax<2050, expressed in the number of generations, was the shortest (assumed confidence level 0.99). The scheduling system allowed the definition of individual machine availability periods and taking into account the restrictions of the transport system (the allowed sequences of palette retrieval).

Słowa kluczowe

PL

szeregowanie; pakowanie; zadanie niepodzielne; ograniczenia zasobów

EN

scheduling; bin packing; genetic algorithm; single machine; resource constrains; manufacturing control

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 9
• Strony: 1093--1096
• Opis fizyczny: Bibliogr. 17 poz., rys., tab., wykr

Twórcy

autor

Cechowicz R.

• Politechnika Lubelska, Katedra Automatyzacji, ul. Nadbystrzycka 36, 20-618 Lublin,

Bibliografia

• [1] Cook S. A.: The complexity of theorem-proving procedures, Proc. 3rd Annual ACM Symp. on the Theory of Computing, 1971.
• [2] Karp R. M.: Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, New York, 1972.
• [3] Johnson D. S., Demers A., Ullman J. D., Garey M. R., Graham R. L.: Worst-Case Performance Bounds For Simple One-Dimensional Packing Algorithms , SIAM J. COM’UT. Vol. 3, No. 4, 1974.
• [4] Xia Binzhou, Tan Zhiyi: Tighter bounds of the First Fit algorithm for the bin-packing problem, Discrete Applied Mathematics 158 (15), 2010.
• [5] Minyi Y.: A simple proof of the inequality FFD(L)≤(11/9)OPT(L+1), for all L, for the FFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica 7 (4), 1991.
• [6] Fleszar K., Charalambous C.: Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem, European Journal of Operational Research, 210, 2011.
• [7] Fleszar K., Hindi K. S.: New Heuristics for One-Dimensional Bin-Packing, Computers and Operations Research, 29:7, 2002.
• [8] Coffman E. G., Jr., Garey M. R., Johnson D. S.: Approximation algorithms for bin packing: a survey. In Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, USA, 1996.
• [9] Csirik J., Johnson D. S., Kenyon C., Shor P. W., Weber R. R.: A Self-Organizing Bin Packing Heuristic, Algorithm Engineering and Experimentation: International Workshop ALENEX’99, Springer Lecture Notes in Computer Science 1619, 1999.
• [10] Schwerin P., Wäscher G.: The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP, International Transactions in Operational Research 4, 1997.
• [11] Falkenauer E.: A Hybrid Grouping Genetic Algorithm for Bin Packing, Working paper CRIF Industrial Management and Automation, 50 av. F. D. Roosevelt, B-1050 Brussels, Belgium, 1994.
• [12] Java Genetic Algorithm Package, http://jgap.sourceforge.net/
• [13] Beasley J. E.: OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/orlib
• [14] Project BINPP, http://www.wiwi.uni-jena.de/Entscheidung/binpp/
• [15] Belov G., Scheithauer G.: A branch&cut&price algorithm for one and two-dimensional two-staged cutting (stock) problems.
• [16] Wróblewski J.: strona http://www.jakubw.pl/sci/binpack/index.html
• [17] Schoenfield J. E.: Fast, exact solution of open bin packing problems without linear programming, US Army Space & Missile Defense Command, Huntsville, Alabama, USA, 2002.