Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity

References

• Avella, Pasquale, Maurizio Boccia, and Igor Vasilyev. 2010. “A Computational Study of Exact Knapsack Separation for the Generalized Assignment Problem.” Computational Optimization and Applications 45 (3): 543–555.
   Web of Science ®Google Scholar
• Benders, J. F., and J. A. E. E. Van Nunen. 1983. “A Property of Assignment Type Mixed Integer Linear Programming Problems.” Operations Research Letters 2 (2): 47–52.
   Web of Science ®Google Scholar
• Boussaïd, Ilhem, Julien Lepagnot, and Patrick Siarry. 2013. “A Survey on Optimization Metaheuristics.” Information Sciences 237: 82–117.
   Web of Science ®Google Scholar
• Cambazard, Hadrien, Pierre-Emmanuel Hladik, Anne-Marie Déplanche, Narendra Jussien, and Yvon Trinquet. 2004. “Decomposition and Learning for a Hard Real Time Task Allocation Problem.” In International Conference on Principles and Practice of Constraint Programming (CP'04), 153–167. Berlin: Springer-Verlag. doi:https://doi.org/10.1007/978-3-540-30201-8_14.
   Google Scholar
• Chalupa, D., and P. Nielsen. 2019. “A Simple and Robust Monte Carlo Hybrid Local Search Algorithm for the Facility Location Problem.” Engineering Optimization 51 (5): 832–845.
   Web of Science ®Google Scholar
• Chu, Paul C., and John E. Beasley. 1997. “A Genetic Algorithm for the Generalised Assignment Problem.” Computers & Operations Research 24 (1): 17–23.
   Web of Science ®Google Scholar
• Dang, Q.-V., I. E. Nielsen, and G. Bocewicz. 2012. “A Genetic Algorithm-Based Heuristic for Part-Feeding Mobile Robot Scheduling Problem.” In Trends in Practical Applications of Agents and Multiagent Systems, Vol. 157 of the book series Advances in Intelligent and Soft Computing, 85–92. Berlin: Springer. doi:https://doi.org/10.1007/978-3-642-28795-4_10.
   Google Scholar
• Defersha, Fantahun M., and Fatemeh Mohebalizadehgashti. 2018. “Simultaneous Balancing, Sequencing, and Workstation Planning for a Mixed Model Manual Assembly Line Using Hybrid Genetic Algorithm.” Computers & Industrial Engineering 119: 370–387.
   Web of Science ®Google Scholar
• Dokeroglu, Tansel, Ender. Sevinc, Tayfun. Kucukyilmaz, and Ahmet. Cosar. 2019. “A Survey on New Generation Metaheuristic Algorithms.” Computers & Industrial Engineering 137: Article ID 106040. doi:https://doi.org/10.1016/j.cie.2019.106040.
   Web of Science ®Google Scholar
• El Yafrani, Mohamed, Marcella S. R. Martins, Mehdi El Krari, Markus Wagner, Myriam R. B. S. Delgado, Belaïd Ahiod, and Ricardo Lüders. 2018. “A Fitness Landscape Analysis of the Travelling Thief Problem.” In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18), 277–284. New York: Association for Computing Machinery. doi:https://doi.org/10.1145/3205455.3205537.
   Google Scholar
• Faccio, Maurizio, Mauro Gamberi, and Marco Bortolini. 2016. “Hierarchical Approach for Paced Mixed-Model Assembly Line Balancing and Sequencing with Jolly Operators.” International Journal of Production Research 54 (3): 761–777. doi:https://doi.org/10.1080/00207543.2015.1059965.
   Web of Science ®Google Scholar
• Fisher, Marshall L., Ramchandran Jaikumar, and Luk N. Van Wassenhove. 1986. “A Multiplier Adjustment Method for the Generalized Assignment Problem.” Management Science 32 (9): 1095–1103.
   Web of Science ®Google Scholar
• Glover, Fred. 1994. “Genetic Algorithms and Scatter Search: Unsuspected Potentials.” Statistics and Computing 4 (2): 131–140.
   Web of Science ®Google Scholar
• Higgins, Andrew J. 2001. “A Dynamic Tabu Search for Large-Scale Generalised Assignment Problems.” Computers & Operations Research 28 (10): 1039–1048.
   Web of Science ®Google Scholar
• Hu, Kuo-Jen. 2017. “Fuzzy Goal Programming Technique for Solving Flexible Assignment Problem in PCB Assembly Line.” Journal of Information and Optimization Sciences 38 (3-4): 423–442.
   Web of Science ®Google Scholar
• Hussain, Kashif, Mohd Najib Mohd Salleh, Shi Cheng, and Yuhui Shi. 2019. “Metaheuristic Research: A Comprehensive Survey.” Artificial Intelligence Review 52 (4): 2191–2233.
   Web of Science ®Google Scholar
• Ishigaki, Aya, and Tomoyuki Miyashita. 2016. “Development of Search Method for Sequencing Problem in Mixed-Model Assembly Lines.” Journal of Advanced Mechanical Design, Systems, and Manufacturing 10 (3): Article ID JAMDSM0048. doi:https://doi.org/10.1299/jamdsm.2016jamdsm0048.
   Web of Science ®Google Scholar
• Jörnsten, K. O., and P. Värbrand. 1991. “A Hybrid Algorithm for the Generalized Assignment Problem.” Optimization 22 (2): 273–282.
   Google Scholar
• Jörnsten, Kurt, and Mikael Näsberg. 1986. “A New Lagrangian Relaxation Approach to the Generalized Assignment Problem.” European Journal of Operational Research 27 (3): 313–323.
   Web of Science ®Google Scholar
• Kucukkoc, Ibrahim, and David Z. Zhang. 2016. “Integrating Ant Colony and Genetic Algorithms in the Balancing and Scheduling of Complex Assembly Lines.” The International Journal of Advanced Manufacturing Technology 82 (1-4): 265–285.
   Web of Science ®Google Scholar
• Li, Zixiang, Mukund Nilakantan Janardhanan, Qiuhua Tang, and Peter Nielsen. 2018. “Mathematical Model and Metaheuristics for Simultaneous Balancing and Sequencing of a Robotic Mixed-Model Assembly Line.” Engineering Optimization 50 (5): 877–893.
   Web of Science ®Google Scholar
• Lourenço, Helena R., Olivier C. Martin, and Thomas Stützle. 2003. “Iterated Local Search.” In Handbook of Metaheuristics, 320–353. Boston, MA: Kluwer Academic. doi:https://doi.org/10.1007/0-306-48056-5_11.
   Google Scholar
• Makarouni, Ioanna, Eleftherios Siskos, and John Psarras. 2016. “Multiobjective Large Scale Job Sequencing Optimization Based on a Synergy of Compensatory and Non Compensatory Methods.” Operational Research 16 (2): 223–244.
   Web of Science ®Google Scholar
• Martello, Silvano. 1981. “An Algorithm for the Generalized Assignment Problem.” Operational Research 1981: 589–603. http://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=PASCAL83X0001931.
   Google Scholar
• Moussavi, S. E., M. Mahdjoub, and O. Grunder. 2018. “A Hybrid Heuristic Algorithm for the Sequencing Generalized Assignment Problem in an Assembly Line.” IFAC-PapersOnLine 51 (2): 695–700.
   Google Scholar
• Moussavi, Seyed-Esmaeil, Morad Mahdjoub, and Olivier Grunder. 2017. “Productivity Improvement through a Sequencing Generalised Assignment in an Assembly Line System.” International Journal of Production Research 55 (24): 7509–7523.
   Web of Science ®Google Scholar
• Ochoa, Gabriela, Marco Tomassini, Sebástien Vérel, and Christian Darabos. 2008. “A Study of NK Landscapes' Basins and Local Optima Networks.” In Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 555–562. New York: Association for Computing Machinery.
   Google Scholar
• Olson, Mancur. 2009. The Logic of Collective Action: Public Goods and the Theory of Groups. Cambridge, MA: Harvard University Press.
   Google Scholar
• Osman, Ibrahim H. 1995. “Heuristics for the Generalised Assignment Problem: Simulated Annealing and Tabu Search Approaches.” Operations-Research-Spektrum 17 (4): 211–225.
   Google Scholar
• Pereira, Jordi, and Eduardo Álvarez-Miranda. 2018. “An Exact Approach for the Robust Assembly Line Balancing Problem.” Omega 78: 85–98.
   Web of Science ®Google Scholar
• Posta, Marius, Jacques A. Ferland, and Philippe Michelon. 2012. “An Exact Method with Variable Fixing for Solving the Generalized Assignment Problem.” Computational Optimization and Applications 52 (3): 629–644.
   Web of Science ®Google Scholar
• Ross, G. Terry, and Richard M. Soland. 1975. “A Branch and Bound Algorithm for the Generalized Assignment Problem.” Mathematical Programming 8 (1): 91–103.
   Web of Science ®Google Scholar
• Souza, Danilo S., Haroldo G. Santos, and Igor M. Coelho. 2017. “A Hybrid Heuristic in GPU-CPU Based on Scatter Search for the Generalized Assignment Problem.” Procedia Computer Science 108: 1404–1413.
   Google Scholar
• Tuncel, Gonca, and Seyda Topaloglu. 2013. “Assembly Line Balancing with Positional Constraints, Task Assignment Restrictions and Station Paralleling: A Case in an Electronics Company.” Computers & Industrial Engineering 64 (2): 602–609.
   Web of Science ®Google Scholar
• Watson, Jean-Paul. 2010. “An Introduction to Fitness Landscape Analysis and Cost Models for local Search.” In Handbook of Metaheuristics, 599–623. Boston, MA: Kluwer Academic. doi:https://doi.org/10.1007/978-1-4419-1665-5_20.
   Google Scholar
• Yagiura, Mutsunori, Toshihide Ibaraki, and Fred Glover. 2004. “An Ejection Chain Approach for the Generalized Assignment Problem.” INFORMS Journal on Computing 16 (2): 133–151.
   Web of Science ®Google Scholar
• Yagiura, Mutsunori, Toshihide Ibaraki, and Fred Glover. 2006. “A Path Relinking Approach with Ejection Chains for the Generalized Assignment Problem.” European Journal of Operational Research 169 (2): 548–569.
   Web of Science ®Google Scholar