Wybrane modele i metody optymalizacji alokacji zasobów

• Autorzy: Pieńkosz K.

Warianty tytułu

EN

Optimization models and methods of resource allocation

• Języki publikacji: PL

Abstrakty

PL

Monografia dotyczy zagadnień związanych z efektywnym rozdziałem szeroko rozumianych zasobów. Prezentowane są metody optymalizacji dla problemów alokacji pojedynczego zasobu, zasobu dostępnego w porcjach o określonej wielkości oraz zestawu różnych rodzajów zasobów. Szczegółowo analizowane są właściwości modeli i algorytmów rozwiązywania dla problemów alokacji formułowanych jako zadania plecakowe, zadania pakowania i rozkroju oraz zagadnienia transportowe i dystrybucyjne. Klasyczne modele alokacji mają głównie charakter dyskretny, wykluczający możliwość częściowej realizacji zapotrzebowań, bądź ciągły z pełną swobodą przydziału zasobu. W pracy szczególną uwagę poświęcono analizie semi-ciągłych problemów rozdziału zasobów i algorytmom ich rozwiązywania. W modelach semi-ciągłych zakłada się, że wielkość przydzielanego zasobu nie może być mniejsza od wartości zadanego parametru β. Tego typu modele były dotychczas badane w literaturze w ograniczonym stopniu, pomimo ich istotnego znaczenia praktycznego i teoretycznego. Stanowią one uogólnienie klasycznych modeli alokacji. Poprzez możliwość wyboru wartości parametru β dostosowanej do rzeczywistych uwarunkowań, pozwalają wyznaczać bardziej elastyczne sposoby gospodarowania zasobami.

EN

The book investigates resource allocation problems. We present models and methods fbr effective allocation of resources among competing activities. Classical discrete optimization models assume that if a resource is allocated to an activity then its demand must be fully satisfied. In continuous models, it is allowed to allocate a very small amount of resource. The main subject of the monograph are semi-continuous models which can be seen as a generalization of the classical discrete and continuous approaches. In semi-continuous models, the amount of resource allocated to an activity cannot be smaller than a given parameter β. In the case when only a single resource is available, the Semi-Continuous Knapsack Problem is formulated and its structural properties are analyzed. As a result, a procedure is developed which enables to fix the optimal values of some variables and transforms the resulting problem of reduced size into the Cardinality Constrained Knapsack Problem. Next, two classes of approximation algorithms are proposed and their performance in the worst case is analyzed. For multi resource allocation problems with uniform resources, the One-Dimensional Semi-Continuous Bin Packing model is formulated. We describe several approximation algorithms for solving such problem and analyze their properties. The results of computational experiments and conclusions relating to the effectiveness of the algorithms are also presented. The Two-Dimensional Bin Packing Problem is discussed only for the discrete case concerning cutting stock process. The application of an approximation algorithm exploiting bottom-up approach and the best-first strategy is described. General multi resource allocation problems are considered in the context of the General Assignment Problem, Transportation Problem and Capacitated Facility Location Problem. The semi-continuous model is discussed mainly for the Transportation Problem. The conditions for existing feasible solutions of semi-continuous model arę formulated. Moreover, an exact algorithm is developed for a special case concerning two resources and sufficiently small β. For the Capacitated Facility Location Problem a Lagrangian heuristic is described and the possibility of its application to the semi-continuous model is discussed.

Słowa kluczowe

PL

alokacja zasobów; optymalizacja; modele semi-ciągłe; zadania plecakowe; problemy pakowania i rozkroju; dystrybucja; lokalizacja

EN

resource allocation; optimization; semi-continuous models; knapsack problems; packing and cutting problems; distribution; facility location

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2010
• Tom: z. 174
• Strony: 3--132
• Opis fizyczny: Bibliogr. 119 poz., tab., rys., wykr.

Twórcy

autor

Pieńkosz K.

• Instytut Automatyki i Informatyki Stosowanej, Politechnika Warszawska

Bibliografia

• [1] Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows, Prentice Hall, Englewood Cliffs, New Jersey, (1993).
• [2] Alvares-Valdes R., Parreno F., Tamarit J.M.: A tabu search algorithm for a two-dimensional non-guillotine cutting problem, European Journal of Operational Research 183, (2007), 1167-1182.
• [3] Barcia P., Jörnsten K.: Improved Lagrangean decomposition: An application to the generalized assignment problem. European Journal of Operational Research 46, (1990), 84-92.
• [4] Barnhart C., Johnson E., Nemhauser G., Savelsbergh M., Vance P.: Branch-and-price: column generation for solving huge integer programs. Operations Research 46, (1998), 316-329.
• [5] Bazaraa M.S., Jarvis J.J., Sherali H.D.: Linear Programming and Network Flows, John Wiley & Sons, New York, (1990).
• [6] Beale E.M.L.: Integer Programming, w Computational Mathematical Programming, red. Schittkowski K., NATO ASI Series, Vol. F15, Springer-Verlag, (1985), 1-24.
• [7] Beasley J.E.: Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operational Research Society 36, (1985), 297-306.
• [8] Beasley J.E.: An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research 33, (1985), 49-64.
• [9] Beasley J.E.: Lagrangean heuristics for location problems. European Journal of Operational Research 65, (1993), 383-399.
• [10] Beasley J.E.: A population heuristic for constrained two-dimensional non-guillotine cutting. European Journal of Operational Research 156 (2004), 601-627.
• [11] Belov G., Scheithauer G.: A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research 171, (2006), 85-106.
• [12] Błażewicz J., Ecker K., Schmidt G., Pesch E., Węglarz J.: Handbook of Scheduling: from Theory to Applications, Springer-Verlag, Berlin, (2007).
• [13] Caprara A., Kellerer H., Pferschy U., Pisinger D.: Approximation algorithms for knapsack problems with cardinality constraints. European Journal of Operational Research 123, (2000), 333-345.
• [14] Caprara A., Monaci M.: On the two-dimensional knapsack problem. Operations Research Letters 32, (2004), 5-14.
• [15] Catrysse D.O., Van Wassenhove L.N.: A survey of algorithms for the generalized assignment problem. European Journal of Operational Research 60, (1992), 260-272.
• [16] Christofides N., Hadjiconstantinou E.: An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. European Journal of Operational Research 83, (1995), 21-38.
• [17] Chu P.C., Beasley J.E.: A genetic algorithm for the generalised assignment problem. Computers and Operations Research 24, (1997), 17-23.
• [18] Coffman R.G., Galambos G., Martello S., Vigo D.: Bin packing approximation algorithms: combinatorial analysis. Handbook of Combinatorial Optimization, red. Du D.Z. i Parados P.M., Kluwer Academic Publishers, (1998), 151-207.
• [19] Cornuejols G., Sridharan R., Thizy J.M.: A Comparison of heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research 50, (1991), 280-297.
• [20] Cung V., Hifi M., Le Cun B.: Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm. International Transactions in Operational Research 7, (2000), 185-210.
• [21] Delmaire D., Diaz J.A., Fernandez E., Ortega M.: Comparing new heuristics for the pure integer capacitated plant location problem. Referat 2nd Metaheuristics International Conference, Nicea, Francja, (1997).
• [22] De Maio A., Rovena C.: An all zero-one algorithm for a certain class of transportation problems. Operations Research 19, (1971), 1406-1418.
• [23] Dell'Amico M., Toth P.: Algorithms and codes for dense assignment problems: the state of art. Discrete Applied Mathematics 100, (2000), 17-48.
• [24] Diaz J.A., Fernandez E.: A tabu search heuristic for the generalized assignment problem. European Journal of Operational Research 132, (2001), 22-38.
• [25] Drezner Z., Hamacher H.W. (ed.): Facility Location, Springer-Verlag, Berlin, (2004).
• [26] Ecker K., Hirschberg R.: Task scheduling with restricted preemptions. Lecture Notes in Computer Science, vol. 694, Springer-Verlag, Berlin, (1993), 464-475.
• [27] Faina L.: An application of simulated annealing to the cutting stock problem. European Journal of Operational Research 114, (1999), 542-556.
• [28] de Farias I.R. Jr, Nemhauser G.L.: A polyhedral study of the cardinality constrained knapsack problem. Mathematical Programming, Ser. A 96, (2003), 439-467.
• [29] de Farias I.R Jr.: Semi-continuous cuts for mixed-integer programming. Lecture Notes in Computer Science, vol. 3064, Springer-Verlag, Berlin, (2004), 163-177.
• [30] Fayard D., Zissimpopoulos V.: An approximation algorithm for solving unconstrained two-dimensional knapsack problems. European Journal of Operational Research 84, (1995), 618-632.
• [31] Fekete S.P., Schepers J.: A new exact algorithm for general orthogonal d-dimensional knapsack problems. Sprinter Lecture Notes in Computer Science 1284, (1997), 144-156.
• [32] Fekete S.P., Schepers J., van der Veen J.: An exact algorithm for higher-dimensional orthogonal packing. Operations Research 55, (2007), 569-587.
• [33] Fisher M.L., Jaikumar R., van Wassenhove L.N.: A multiplier adjustment method for the generalized assignment problem. Management Science 32, (1986), 1095-1103.
• [34] Fleszar K., Hindi K.S.: New heuristics for one-dimensional bin packing. Computers and Operations Research 29, (2002), 821-839.
• [35] Garey M.R., Johnson D.S: Computers and Intractability; A Guide to the Theory of NP-completeness, Freeman, San Francisco, (1979).
• [36] Geoffrion A.M.: Lagrangian relaxation and its uses in integer programming. Mathematical Programming Study 2, (1974), 82-114.
• [37] Geoffrion A.M., Graves G.W: Multicommodity distribution system design by Benders decomposition. Management Science 20, (1974), 822-844.
• [38] Gilmore P.G., Gomory R.E.: A linear approach to the cutting-stock problem. Operations Research 9, (1961), 849-859.
• [39] Goncalves J.F.: A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem. European Journal of Operational Research 183, (2007), 1212-1229.
• [40] Haddadi S., Ouzia H.: Effective algorithm and heuristic for the generalized assignment problem. European Journal of Operational Research 153, (2004), 184-190.
• [41] Hadjiconstantinou E., Christofides N.: An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research 83, (1995), 39-56.
• [42] Hadjiconstantinou E., Iori M.: A hybrid algorithm for the two-dimensional single large object placement problem. European Journal of Operational Research 183, (2007), 1150-1166.
• [43] Held M., Wolte R, Crowder H.R: Validation of subgradient optimization. Mathematical Programming 6, (1974), 62-66,
• [44] Hifi M., Zissimopoulos V.: A recursive exact algorithm for weighted two-dimensional cutting. European Journal of Operational Research 91, (1996), 553-564.
• [45] Hifi M.: An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock. Computers and Operations Research 24, (1997), 727-736.
• [46] Hifi M., M'Hallah R.: Strip generation algorithms for constrained two-dimensional two-staged cutting problems, European Journal of Operational Research 172, (2006), 515-527.
• [47] Higgins A.J.: A dynamic tabu search for large-scale generalised assignment problems. Computers and Operations Research 28, (2001), 1039-1048.
• [48] Hindi K.S., Basta T.: Computationally efficient solution of a multiproduct, two-stage distribution-location problem. Journal of the Operational Research Society 45, (1994), 1316-1323.
• [49] Hindi K.S., Basta T., Pieńkosz K.: Efficient solution of a multi-commodity two-stage distribution problem with constraints on assignment of customers to distribution centers. International Transactions in Operational Research 5, (1998), 519-527.
• [50] Hindi K.S., Pieńkosz, K.: Efficient solution of large scale, single-source, capacitated plant location problems. Journal of the Operational Research Society 50, (1999), 268-274.
• [51] Holmberg K., Rönnqvist M., Yuan D.: An exact algorithm for the capacitated facility location problems with single sourcing. European Journal of Operational Research 113, (1999), 544-559.
• [52] Ibaraki T., Katoh N.: Resource Allocation Problems: Algorithmic Approaches, The MIT Press, Cambridge, (1988).
• [53] ILOG Solver 4.3 User's Manual, ILOG 1998.
• [54] ILOG Cplex 9.1 User's Manual, ILOG 2005.
• [55] Jeet V., Kutanoglu E.: Lagrangian relaxation guided problem space search heuristics for generalized assignment problems. European Journal of Operational Research 182, (2007), 1039-1056.
• [56] 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 Journal on Computing 3, (1974), 299-325.
• [57] Jörnsten K., Näsberg M.: A new Lagrangean relaxation approach to the generalized assignment problem. European Journal of Operational Research 27, (1986), 313-323.
• [58] Józefowska J.,Węglarz, J.: On a methodology for discrete-continuous scheduling problems. European Journal of Operational Research 107, (1998), 338-353.
• [59] Józefowska J., Mika M., Różycki R., Waligóra G., Węglarz J.: Project scheduling under discrete and continuous resources, w Project Scheduling: Recent Models, Algorithms and Applications, red. Węglarz J., Kluwer, Boston, (1999), 289-308.
• [60] Katoh N., Ibaraki T.: Resource allocation problems, w Handbook of Combinatorial Optimization vol. 2, red. Du D.Z. i Parados P.M., Kluwer Academic Publishers, (1998), 159-260.
• [61] Kellerer H., Pferschy U., Pisinger D.: Knapsack Problems, Springer-Verlag, Berlin, (2004).
• [62] Klose A.: An LP-based heuristic for two-stage capacitated facility location problems. Journal of the Operational Research Society 50, (1999), 157-166.
• [63] Klose A.: A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem. European Journal of Operational Research 126, (2000), 408-421.
• [64] Klose A., Drexl A.: Facility location models for distribution system design. European Journal of Operational Research 162, (2005), 4-29.
• [65] Klose A., Gortz S.: A branch-and-price algorithm for the capacitated facility location problem. European Journal of Operational Research 179, (2007), 1109-1125.
• [66] Lai K.K., Chan J.W.M.: Developing a simulated annealing algorithm for the cutting stock problem. Computers and Industrial Engineering 32, (1997), 115-127.
• [67] Lodi A., Monaci M.: Integer linear programming models for 2-staged two-dimensional knapsak problems. Mathematical Programming 94, (2003), 257-278.
• [68] Lodi A., Martello S., Monaci M.: Two-dimensional packing problems: A survey. European Journal of Operational Research 141, (2002), 241-252.
• [69] Lodi A., Martello S., Vigo D.: Recent advances on two-dimensional bin packing problems. European Journal of Operational Research 123, (2002), 379-396.
• [70] Luss H.: On equitable resource allocation problems: a lexicographic minimax approach. Operations Research 47, (1999), 361-378.
• [71] Mandal C.C., Chakrabarti P.P., Ghose S.: Complexity of fragmentable object bin packing and an application. Computers and Mathematics with Applications 35, (1998), 91-97.
• [72] Martello S., Toth P.: Knapsack Problems, John Wiley and Sons, New York, (1990).
• [73] Martello S., Toth P.: Upper bounds and algorithms for hard 0-1 knapsack problems. Operations Research 45, (1997), 768-778.
• [74] Martello S., Pisinger D., Toth P.: New trends in exact algorithms for 0-1 knapsack problem. European Journal of Operational Research 123, (2000), 325-332.
• [75] Martello S., Vigo D.: Exact solution of the two-dimensional finite bin packing problem. Management Science 44, (1998), 388-399.
• [76] Menakerman N., Rom R.: Bin Packing with Item Fragmentation. Lecture Notes in Computer Science vol. 2125, Springer-Verlag, Berlin, (2001), 313-324.
• [77] Morales D.R, Romeijn H.E.: The generalized assignment problem and extensions, w Handbook of Combinatorial Optimization, red. Du D.Z, Pardalos P.M., supplement B, (2004), 259-311.
• [78] Nagelhout R.V., Thomson G.L: A single source transportation algorithm. Computers and Operations Research 7, (1980), 185-198.
• [79] Narciso M.G., Lorena L.A.N.: Lagrangean/surrogate relaxation for generalized assignment problems. European Journal of Operational Research 114, (1999), 165-177.
• [80] Ogryczak W.: Bicriteria models for fair resource allocation. Proceedings on the 1st International Workshop on Computational Social Choice, (2006), 380-393.
• [81] Osman I.H.: Heuristics for the generalised assignment problem: simulated annealing and tabu search approaches. OR Spektrum 17, (1995), 21 1-225.
• [82] Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall Inc., (1982).
• [83] Patriksson M.: A survey on the continuous nonlinear resource allocation problem. European Journal of Operational Research 185, (2008), 1-46.
• [84] Pearl J.: Heuristics, Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Publishing Company Inc., (1984).
• [85] Pieńkosz K., Toczyłowski E.: Regularyzacje metod agregacji zadań harmonogramowania w jednostopniowych systemach produkcyjnych. Zeszyty Naukowe Politechniki Śląskiej, ser. Automatyka z. 109, (1992), 183-192.
• [86] Pieńkosz K., Toczyłowski E.: On aggregation of items in single-stage production systems with limited inventory levels. Operations Research 41, (1993), 419-426.
• [87] Pieńkosz K.: Komputerowy system optymalizacji rozkroju szklanych tafli. Zeszyty Naukowe Politechniki Śląskiej, ser. Automatyka z. l 18, (1996), 165-173.
• [88] Pieńkosz, K.: Metoda rozwiązywania problemu dystrybucyjnego z wykorzystaniem relaksacji Lagrange’a. Zeszyty Naukowe Politechniki Śląskiej, ser. Automatyka z. 123, (1998), 277-286.
• [89] Pieńkosz, K., Zadora-Przyłecki K.: On efficiency of ILOG software in application to combinatorial problems. Proceedings of the Workshop on Constraint Programming for Decision and Control, (1999), 35-40.
• [90] Pieńkosz K.: Porównanie metod optymalizacji procesów dyskretnych na przykładzie uogólnionego zadania przydziału. Automatyka tom 3, zeszyt 1, (1999), 281-287.
• [91] Pieńkosz K.: Programowanie w logice ograniczeń w zastosowaniu do optymalizacji decyzji. Zeszyty Naukowe Wydziału Mechanicznego Nr 31, Politechnika Koszalińska, (2002), 135-142.
• [92] Pieńkosz K., Tratkiewicz K.: Problem optymalizacji rozkroju i spawania kształtowników. Zeszyty Naukowe Wydziału Mechanicznego Nr 35, Politechnika Koszalińska, (2004), 193-200.
• [93] Pieńkosz K., Tratkiewicz K.: Algorytmy heurystyczne dla jednowymiarowego problemu pakowania z ograniczoną podzielnością elementów, w Automatyzacja procesów dyskretnych, red. Gessing R. i Szkodny T., rozdział XIX, WNT Warszawa, (2004), 177-183.
• [94] Pieńkosz K.: On solving the semi-continuous knapsack problem. Proceedings of the 11th IEEE International Conference on Methods and Models in Automation and Robotics MMAR2005, (2005), 851-855.
• [95] Pieńkosz K.: Właściwości rozwiązań problemu plecakowego z ograniczoną podzielnością elementów. Zeszyty Naukowe Politechniki Śląskiej, ser. Automatyka z. 144, (2006), 189-195.
• [96] Pieńkosz K.: Problem ograniczonej alokacji zasobu i właściwości jego rozwiązań, w Sterowanie i automatyzacja: aktualne problemy i ich rozwiązania, red. Malinowski K. i Rutkowski L., rozdział XIX, Akademicka Oficyna Wydawnicza EXIT, Warszawa, (2008), 322-329.
• [97] Pieńkosz K.: Heurystyczne algorytmy ograniczonej alokacji zasobu. Przegląd Elektrotechniczny 9, (2008), 89-92.
• [98] Pirkul H., Jayaraman V.: A multi-commodity, multi-plant, capacitated facility location problem: Formulation and efficient heuristic solution. Computers and Operations Research 25, (1998), 869-878.
• [99] Pisinger D.: Where are the hard knapsack problems? Computers and Operations Research 32, (2005), 2271-2284.
• [100] Ross G.T., Soland R.M.: A branch and bound algorithm for the generalized assignment problem. Mathematical Programming 8, (1975), 91-103.
• [101] Savelsbergh M.: A branch-and-price algorithm for the generalized assignment problem. Operations Research 6, (1997), 831-841.
• [102] Scholl A., Klein R., Jurgens C.: BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers and Operations Research 24, (1997), 627-645.
• [103] Sharma R.R.K., Prasad S.: Obtaining a good primal solution to the uncapacitated transportation problem. European Journal of Operational Research 144, (2003), 560-564.
• [104] Srinivasan V., Thompson G.L.: An algorithm for assigning uses to sources in a special class of transportation problems. Operations Research 21, (1973), 284-295.
• [105] Sridharan R.: A Lagrangian heuristic for the capacitated plant location problem with single source constraints. European Journal of Operational Research 66, (1993), 305-312.
• [106] Toczyłowski E.: Niektóre metody strukturalne optymalizacji do sterowania w dyskretnych systemach wytwarzania, WNT, Warszawa, (1989).
• [107] Tomżyński K.D.: Heurystyczne algorytmy rozwiązywania problemu plecakowego z ograniczoną liczbą pakowanych elementów, praca inżynierska, Wydział Elektroniki i Technik Informacyjnych, Politechnika Warszawska, (2009).
• [108] Tragantalerngsak S., Holt J., Rönnqvist M.: An exact method for the two-echelon, single-source, capacitated facility location problem, European Journal of Operational Research 123 (2000), 473-489.
• [109] Tratkiewicz K.: Modele i algorytmy optymalizacji rozkroju i spawania kształtowników, praca magisterska, Wydział Elektroniki i Technik Informacyjnych, Politechnika Warszawska, (2004).
• [110] Valerio de Carvalho J.M.: Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research 86, (1999), 629-659.
• [111] Vanderbeck R: Computational study of a column generation algorithm for bin packing and cutting stock problems. Mathematical Programming Ser. A86, (1999), 565-594.
• [112] Van Hentenryck P.: Constraint Satisfaction in Logic Programming, The MIT Press, (1989).
• [113] Viswanathan K.V., Bagchi A.: Best-first search methods for constrained two-dimensional cutting stock problems. Operations Research 41, (1993), 768-776.
• [114] Walukiewicz S., Programowanie dyskretne, PWN Warszawa, (1986).
• [115] Wang P.Y.: Tzwo algorithms for constrained two-dimensional cutting stock problems. Operations Research, 31, (1983), 573-586.
• [116] Wäscher G., Hauβner H., Schumann H.: An improved typology of cutting and packing problems. European Journal of Operational Research 183 (2007), 1109-1130.
• [117] Wolsey A.: Integer programming. John Wiley and Sons, New York, (1998).
• [118] Yaiura M., Ibaraki T., Glover F.: A path relinking approach with ejection chains for the generalized assignment problem. European Journal of Operational Research 169 (2006), 548-569.
• [119] Yue M.: A simple proof of the inequality FFD(L) ≤ 11/9 OPT(L) + l VL for the FFD bin packing algorithm. Acta Mathematica Sinica 7, (1991), 321-331.