An analysis of Problem Solving II – Advanced Assignment Variants
DOI:
https://doi.org/10.29070/eg26r024Keywords:
Multi-objective optimization, Generalized assignment problem, Heuristic lower bounds, Lagrangian relaxation, Pareto efficiencyAbstract
The evolution of modern manufacturing and logistics systems requires advanced mathematical frameworks capable of handling complex resource allocation challenges. This study investigates multi-objective, many-to-one generalized assignment problems characterized by constrained resource capacities, parameter uncertainties, and conflicting operational goals, including cost minimization, profit maximization, and makespan reduction. To mitigate the exponential computational complexity inherent in these NP-hard formulations, a hybrid optimization framework is proposed that integrates linear relaxations, greedy heuristics, Lagrangian relaxation, and scalarization-based techniques to establish robust lower-bound strategies. Numerical case studies involving interval-valued data demonstrate that the proposed approach substantially accelerates convergence rates and reduces search effort while generating stable, high-quality Pareto-optimal trade-offs. Ultimately, this framework provides a comprehensive, computationally efficient solution for realistic resource scheduling under shifting operational conditions
Downloads
References
1. Alkayal, E. (2018). Optimizing resource allocation using multi-objective particle swarm optimization in cloud computing systems (Doctoral dissertation, University of Southampton). ePrints Soton.
2. Anvari, S., & Turkay, M. (2017). The facility location problem from the perspective of triple bottom line accounting of sustainability. International Journal of Production Research, 55(21), 6266–6287. [https://doi.org/10.1080/00207543.2017.1341632](https://doi.org/10.1080/00207543.2017.1341632)
3. Cattrysse, D. G., & Van Wassenhove, L. N. (1992). A survey of algorithms for the generalized assignment problem. European Journal of Operational Research, 60(3), 260–272. [https://doi.org/10.1016/0377-2217(92)90077-M](https://doi.org/10.1016/0377-2217(92)90077-M)
4. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197. [https://doi.org/10.1109/4235.996017](https://doi.org/10.1109/4235.996017)
5. Díaz, J. A., & Fernández, E. (2002). A tabu search heuristic for the generalized assignment problem with multiple objectives. Journal of Heuristics, 8(4), 407–430. [https://doi.org/10.1023/A:1015481708899](https://doi.org/10.1023/A:1015481708899)
6. Florios, K., & Mavrotas, G. (2014). Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems. Applied Mathematics and Computation, 237, 1–19. [https://doi.org/10.1016/j.amc.2014.03.110](https://doi.org/10.1016/j.amc.2014.03.110)
7. Holzmann, T., & Smith, J. C. (2018). Solving discrete multi-objective optimization problems using modified augmented weighted Tchebychev scalarizations. European Journal of Operational Research, 271(2), 436–449. [https://doi.org/10.1016/j.ejor.2018.05.041](https://doi.org/10.1016/j.ejor.2018.05.041)
8. Jaszkiewicz, A. (2018). Many-objective Pareto local search. European Journal of Operational Research, 271(3), 1001–1013. [https://doi.org/10.1016/j.ejor.2018.05.060](https://doi.org/10.1016/j.ejor.2018.05.060)
9. Konur, D., Farhangi, H., & Dagli, C. H. (2016). A multi-objective military system of systems architecting problem with inflexible and flexible systems: formulation and solution methods. OR Spectrum, 38(4), 967–1006. [https://doi.org/10.1007/s00291-016-0437-0](https://doi.org/10.1007/s00291-016-0437-0)
10. Lourenço, L. L., Armentano, V. A., & Laguna, M. (2001). A multi-objective heuristic for the generalized assignment problem. Journal of the Operational Research Society, 52(11), 1243–1253. [https://doi.org/10.1057/palgrave.jors.2601217](https://doi.org/10.1057/palgrave.jors.2601217)
11. Mavrotas, G. (2009). Effective implementation of the $epsilon$-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation, 213(2), 455–465. [https://doi.org/10.1016/j.amc.2009.03.037](https://doi.org/10.1016/j.amc.2009.03.037)
12. Ngo, T. S., Jaafar, J., Aziz, I. A., Aftab, M. U., Nguyen, H. Giang, & Bui, N. A. (2022). Metaheuristic algorithms based on compromise programming for the multi-objective urban shipment problem. Entropy, 24(3), 388. [https://doi.org/10.3390/e24030388](https://doi.org/10.3390/e24030388)
13. Ngulo, U. (2021). Decomposition methods for combinatorial optimization (Doctoral dissertation, Linköping University). DiVA Portal.
14. Öztürk, D. T., & Köksalan, M. (2016). An interactive approach for biobjective integer programs under quasiconvex preference functions. Annals of Operations Research, 244(2), 677–696. [https://doi.org/10.1007/s10479-015-2092-2](https://doi.org/10.1007/s10479-015-2092-2)
15. Ross, G. T., & Soland, R. M. (1975). A branch and bound algorithm for the generalized assignment problem. Mathematical Programming, 8(1), 91–103. [https://doi.org/10.1007/BF01580430](https://doi.org/10.1007/BF01580430)
16. Shresthamali, S., Kondo, M., & Nakamura, H. (2022). Multi-objective resource scheduling for IoT systems using reinforcement learning. Journal of Low Power Electronics and Applications, 12(4), 53. [https://doi.org/10.3390/jlpea12040053](https://doi.org/10.3390/jlpea12040053)
17. Tariri, G. (2013). The assignment problem with dependent costs (Doctoral dissertation, University of Louisville). ThinkIR.
18. Wang, Y. (2025). Research on multi-objective emergency resource scheduling optimization in chemical industrial parks. PMC Operational Systems, Article PMC12483207.
19. Weerasena, L., Ebiefung, A., & Skjellum, A. (2022). Design of a heuristic algorithm for the generalized multi-objective set covering problem. Computational Optimization and Applications, 82(3), 717–751. [https://doi.org/10.1007/s10589-022-00366-4](https://doi.org/10.1007/s10589-022-00366-4)
20. Wu, L., Zhao, T., & Cai, X. (2026). Interval multi-objective multi-task production scheduling method for manufacturing uncertainty. International Journal of Software Engineering and Knowledge Engineering, 36(12), 2650018X. [https://doi.org/10.1142/S021819402650018X](https://doi.org/10.1142/S021819402650018X)
21. Yagmahan, B., & Yenisey, M. M. (2010). A multi-objective ant colony system algorithm for flow shop scheduling problems. Expert Systems with Applications, 37(2), 1361–1368. [https://doi.org/10.1016/j.eswa.2009.06.104](https://doi.org/10.1016/j.eswa.2009.06.104)
22. Zhang, W., Bao, X., Hao, X., & Gen, M. (2025). Metaheuristics for multi-objective scheduling problems in industry 4.0 and 5.0: a state-of-the-arts survey. Frontiers in Industrial Engineering, 3, Article 1540022. [https://doi.org/10.3389/fieng.2025.1540022](https://doi.org/10.3389/fieng.2025.1540022)
