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

Springer Science and Business Media LLC - Tập 17 - Trang 211-225 - 1995
Ibrahim H. Osman1
1Institute of Mathematics and Statistics, University of Kent, Canterbury, UK

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 ưu

Tà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