Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các phương pháp heuristic cho bài toán phân công tổng quát: phương pháp làm mát mô phỏng và tìm kiếm tabu
Tóm tắt
Bài toán phân công tổng quát (Generalised Assignment Problem - GAP) là bài toán tìm kiếm một phân công có chi phí tối thiểu giữa một tập hợp công việc và một tập hợp tác nhân. Mỗi công việc được phân công cho chính xác một tác nhân. Tổng nhu cầu của tất cả các công việc được phân công cho bất kỳ tác nhân nào không được vượt quá tổng tài nguyên sẵn có cho tác nhân đó. Bài báo này trình bày một cái nhìn tổng quan về các phương pháp chính xác và heuristic. Một cơ chế sinh λ được giới thiệu. Các chiến lược tìm kiếm khác nhau và cài đặt tham số đã được nghiên cứu cho phương pháp giảm độ sâu λ-generation, làm mát mô phỏng kết hợp / tìm kiếm tabu và các phương pháp heuristic tìm kiếm tabu. Các phương pháp đã phát triển tích hợp nhiều đặc điểm đã được chứng minh là hữu ích trong việc đạt được các giải pháp tối ưu và gần tối ưu. Hiệu quả của các phương pháp của chúng tôi được khẳng định bằng cách so sánh hiệu suất của chúng về chất lượng giải pháp và yêu cầu tính toán với các phương pháp tìm kiếm cây nhánh và ràng buộc chuyên biệt khác, làm mát mô phỏng và ý tưởng phânPartition trên một tập hợp các bài toán tiêu chuẩn từ tài liệu.
Từ khóa
#bài toán phân công tổng quát #phương pháp heuristic #làm mát mô phỏng #tìm kiếm tabu #giải pháp tối ưuTài liệu tham khảo
Aarts EHL, Korst J (1988) Simulated annealing and boltzmann machines. Wiley and Sons, Chichester
Amini MM, Racer M (1994) A rigourous computational comparison of alternative solution methods for the generalized assignment problem. Manag Sci 40:868–890
Balas E, Martin CH (1980) Pivot and complement — a heuristic for 0/1 programming. Manag Sci 26:86–96
Barcia P, Holm S (1988) A revised bound improvement sequence algorithm. Eur J Oper Res 36:202–206
Barcia P, Jörnsten K (1990) Improved Lagrangean decomposition: An application to the generalised assignment problem. Eur J Oper Res 46:84–92
Beasley JE (1990) OR-library: distribution test problems by electronic mail. Library email address using anonymous ftp:mscmga.ms.ic.ac.uk. J Oper Res Soc 41:1069–1072
Benders JF, Van Nunen JA (1983) A property of assignment type mixed linear programming problems. Oper Res Lett 2:47–52
Cattrysse DG (1990) Set partitioning approaches to combinatorial optimization problems. Ph. D. Thesis, Katholieke Universiteit Leuven, Departement Wertuigkunde, Centrum Industrieel Beleid, Belgium
Cattrysse DG, Van Wassenhove LN (1992) A survey of algorithms for the generalized assignment problem. Eur J Oper Res 60:260–272
Cattrysse DG, Salomon M, Van Wassenhove LN (1994) A set partitioning heuristic for the generalized assignment problem. Eur J Oper Res 72:167–174
Collins NE, Eglese RW, Golden BL (1988) Simulated annealing: An annotated bibliography. Am J Math Manag Sci 8:209–307
Dammeyer D, Voß S (1993) Dynamic tabu list management using the reverse elimination method. Ann Oper Res 41:31–46
De Werra D, Hertz A (1989) Tabu search techniques: A tutorial and an application to neural networks. OR Spektrum 11:131–141
Dyer M, Frieze A (1990) Probabilistic analysis of the generalized assignment problem. Math Program 55:169–181
Fang L, Li T (1990) Design of competition based neural networks for combinatorial optimization. Int J Neural System 3:221–235
Fisher M, Jaikumar R, Van Wassenhove L (1986) A multiplier adjustment method for the generalised assignment problem. Manag Sci 32:1095–1103
Fisher M, Jaikumar R (1981) A generalised assignment heuristic for the large scale vehicle routing. Networks 11:109–124
Gavish B, Pirkul H (1991) Algorithms for the multi-resource generalized assignment problem. Manag Sci 37:695–713
Gheysens F, Golden BL, Assad A (1984) A comparison of techniques for solving the fleet size and mix vehicle routing problem. OR Spektrum 6:207–216
Glover F (1986) Future path for integer programming and links to artificial intelligence. Comput Oper Res 13:533–549
Glover F (1989) Tabu search part I. ORSA J Comput 1:190–206
Glover F (1990) Tabu search part II. ORSA J Comput 2:4–32
Glover F, Laguna M (1993) Tabu search. In: Modern heuristic techniques for combinatorial problems Reeves CR (ed). Blackwell, Oxford, U.K., pp 70–150
Glover F, Laguna M, Taillard E, de Werra D (1993) Tabu search. Annals of Operations Research 41:Baltzer AG, Switzerland
Glover F, Taillard E, de Werra D (1993) A user's guide to tabu search. Ann Oper Res 41:3–28
Gottlieb ES, Rao MR (1990) (1,K)-Configuration facets for the generalized assignment problem. Math Program 46:53–60
Gottlieb ES, Rao MR (1990) The generalized assignment problem — valid inequalities and facets. Math Program 46:31–52
Guinard M, Rosenwein MB (1989) An improved dual based algorithm for the generalised assigment problem. Oper Res 17:658–663
Hallefjord A, Jörnsten KO, Värbrand P (1993) Solving large scale generalised assignment problem. Oper Res 64:103–104
Hasan M, Osman IH (1995) Local search strategies for the maximal planar graph. Int Transact Oper Res 2:(1) forthcoming
Jänicke W (1989) Optimal assignment of orders to parallel working subplants without splitting. Computer-Integrated Manufacturing Syst 2:186–187
Jörnsten KO, Näsberg M (1986) A new lagrangean relaxation approach to the generalised assignment problem. Eur J Oper Res 27:313–323
Jörnsten KO, Värbrand P (1990) Relaxation techniques and valid inequalities applied to the generalized assignment problem. Asia-Pacific Oper Res 7:172–189
Jörnsten KO, Värbrand P (1991) A hybrid algorithm for the genralized assignment problem. Optimization 2:273–282
Kirkpatrick S, Gelatt JR. CD, Vecchi PM (1983) Optimization by simulated annealing. Science 220:671–680
Klastorin TD (1979) An effective sub-gradient algorithm for the generalised assignment problem. Cumput Oper Res 6:155–164
Klastorin TD (1979) On the maximal covering location problem and the generalized assignment problem. Manag Sci 25:107–112
Laguna M, Kelly JP, Gonzalez-Velarde JL, Glover F (1995) Tabu search for the multilevel assignment problem. Eur J Oper Res 95:(82)170
Laporte G, Osman IH (1995) Metaheuristics in combinatorial optimization. Annals of Operations Research, Baltzer AG, Switzerland. (forthcoming)
Lee MK (1992) A storage assignment policy in a man-on-board automated storage/retrieval system. Int J Prod Res 30:2281–2292
Martello S, Toth P (1981) An algorithm for the generalised assignment problem. In proceedings of the 9th IFORS conference, Hamburg, Germany
Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley and Sons, Chichester
Martello S, Toth P (1992) Generalized assignment problems. Lecture Notes, In Computer Science 660:351–369
Mazzola JB (1989) Generalized assignment with nonlinear capacity interaction. Manag Sci 35:923–941
Mazzola JB, Neebe AW (1993) An algorithm for the bottleneck generalized assignment problem. Comput Oper Res 20:355–362
Osman IH (1990) A comparison of heuristics for the generalised assignment problem. Research Report, University of Kent, Canterbury. Presented at IFORS 90, Athens
Osman IH (1991) Metastrategy simulated annealing and tabu search for combinatorial optimization problems. Ph. D. Thesis, The Management School, Imperial College, University of London
Osman IH (1993) Metastrategy simulated annealing and tabu search algorithm for the vehicle routing problem. Ann Oper Res 41:421–451
Osman IH, Christofides N (1994) Capacitated clustering problems by hybrid simulated annealing and tabu search. Int Transact Oper Res 1:317–336
Osman IH, Laporte G (1995) Modern Heuristics for combinatorial optimization problems. An annotated bibliography. Ann Oper Res (forthcoming)
Osman IH, Pott CN (1989) Simulated annealing for permutation flow-shop scheduling. Omega 17:551–557
Osman IH, Salhi S (1994) Heuristics for the vehicle fleet mix problem. Proceedings of TRISTAN II, Capri, Italy. Bianco L, (editor) I.A.S.I.-C.N.R. Viale Manzoni 30, 00185 Rome, Italy. Part I:67–72
Pesch E, Voß S (1995) Applied local search. OR Spektrum 17:55–65
Racer M, Amini M (1994) A robust heuristic for the generalized assignment problem. Ann Oper Res 50:487–503
Reeves CR (1993) Modern heuristic techniques for combinatorial problems. Blackwell, Oxford
Ross GT, Soland RM (1975) A branch and bound algorithm for the generalised assignment problem. Math Program 8:91–103
Ross GT, Soland RM (1977) Modelling facility location problems as generalised assignment problems. Manag Sci 24:345–357
Savelsbergh MWP (1993) A branch-and-price algorithm for the generalized assignment problem, Report COC-93-02, Computational Optimization Centre, Georgia Institute of Technology, Atlanta, Georgia, USA
Shtub A (198) Modelling group technology cell formation as a generalized assignment problem. Int J Prod Res 27:775–782
Skorin-Kapov J (1990) Tabu search applied to the quadratic assignment problem. ORSA J Comput 2:33–45
Thangiah SR, Osman IH, Vinayagamoorthy R, Sun T (1993) Algorithms for Vehicle Routing Problems With Time Deadlines. Am J Math Manag Sci 13:323–357
Thangiah SR, Osman IH, Sun T (1994) Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems With Time Windows. Working Paper UKC/IMS/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, UK
Trick MA (1992) A linear relaxation heuristic for the generalized assignment problem. Naval Res Logist 39:137–151
Van Laarhoven PJM, Aarts EHL (1987) Simulated annealing theory and applications. Reidel, Dordrecht
Zimokha VA, Rubinshtein MI (1988) R & D planning and the generalised assignment problem. Automation and Remote Control 49:484–492