Keywords:-
Article Content:-
Abstract
The classical assignment problem allocates jobs to agents while optimizing a single performance criterion. Modern allocation decisions often require simultaneous consideration of economic, operational, resource, and environmental consequences. This paper formulates a four-objective multi-objective assignment problem in which total cost, total completion time, resource consumption, and environmental impact are minimized simultaneously. Binary integer programming is developed for assigning (n) tasks to (n) agents subject to one-to-one assignment constraints. Each task-agent combination is characterized by four coefficients representing cost, time, resource consumption, and environmental burden. Since these objectives may conflict, a single solution that independently minimizes all criteria generally does not exist. The Lexicographic Method is adopted to incorporate explicit priority information from the decision maker. The model provides a transparent framework for sustainable task allocation and can be applied to workforce, machine, logistics, project, and service assignment environments. A numerical instance demonstrates the sequential optimization procedure and resulting trade-offs.
References:-
References
Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2), 83–97. DOI: https://doi.org/10.1002/nav.3800020109
Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38. DOI: https://doi.org/10.1137/0105003
Burkard, R. E., Dell’Amico, M., & Martello, S. (2012). Assignment Problems: Revised Reprint. SIAM. DOI: https://doi.org/10.1137/1.9781611972238
Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. Wiley.
Ehrgott, M. (2005). Multicriteria Optimization. Springer. DOI: https://doi.org/10.1007/3-54027659-9
Marler, R. T., & Arora, J. S. (2004). Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization, 26, 369–395. DOI: https://doi.org/10.1007/s00158-003-0368-6
Ulungu, E. L., & Teghem, J. (1994). Multi-objective combinatorial optimization problems: A survey. Journal of Multi-Criteria Decision Analysis, 3(2), 83–104.
DOI: https://doi.org/10.1002/mcda.4020030204
Ehrgott, M., & Gandibleux, X. (2000/2003). A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum, 22, 425–460. DOI: https://doi.org/10.1007/s002910000046
Przybylski, A., Gandibleux, X., & Ehrgott, M. (2008). Two phase algorithms for the bi-objective assignment problem. European Journal of Operational Research, 185(2), 509–533. DOI: https://doi.org/10.1016/j.ejor.2006.12.054
Przybylski, A., Gandibleux, X., & Ehrgott, M. (2010). A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives. Discrete Optimization, 7(3), 149–165. DOI: https://doi.org/10.1016/j.disopt.2010.03.005
Schaffer, J. D. (1985). Multiple objective optimization with vector evaluated genetic algorithms. In Proceedings of the First International Conference on Genetic Algorithms, 93–100.
Srinivas, N., & Deb, K. (1994). Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 2(3), 221–248.
DOI: https://doi.org/10.1162/evco.1994.2.3.221
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. DOI: https://doi.org/10.1109/4235.996017
Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, 8(2), 173–195.
DOI: https://doi.org/10.1162/106365600568202
Das, I., & Dennis, J. E. (1998). Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 8(3), 631–657.
DOI: https://doi.org/10.1137/S1052623496307510
Das, I., & Dennis, J. E. (1997). A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems. Structural Optimization, 14, 63–69. DOI: https://doi.org/10.1007/BF01197559
Athan, T. W., & Papalambros, P. Y. (1996). A note on weighted criteria methods for compromise solutions in multi-objective optimization. Engineering Optimization, 27(2), 155–176. DOI: https://doi.org/10.1080/03052159608941404
Charnes, A., & Cooper, W. W. (1977). Goal programming and multiple objective optimizations: Part 1. European Journal of Operational Research, 1(1), 39–54. DOI:
https://doi.org/10.1016/S03772217(77)81007-2
Rentmeesters, M. J., Tsai, W. K., & Lin, K.-J. (1996). A theory of lexicographic multi-criteria optimization. Proceedings of the IEEE International Conference on Engineering of Complex Computer Systems, 76–79. DOI: https://doi.org/10.1109/ICECCS.1996.558386
Lai, L., Fiaschi, L., Cococcioni, M., et al. (2023). Pure and mixed lexicographic-paretian many-objective optimization: State of the art. Natural Computing, 22, 227–242.
DOI: https://doi.org/10.1007/s11047-022-09911-4
Tappenden, R., et al. (2018). Lexicographic multi-objective linear programming using Grossone methodology: Theory and algorithm. Applied Mathematics and Computation, 318, 298–311. DOI: https://doi.org/10.1016/j.amc.2017.05.058
Liu, R., Liu, M., Chu, F., et al. (2021). Eco-friendly multi-skilled worker assignment and assembly line balancing problem. Computers & Industrial Engineering, 151, 106944. DOI: https://doi.org/10.1016/j.cie.2020.106944
Abido, M. A. (2003). A niched Pareto genetic algorithm for multiobjective environmental/economic dispatch. International Journal of Electrical Power & Energy Systems, 25(2), 97–105. DOI: https://doi.org/10.1016/S0142-0615(02)00027-3
Tang, X., Wu, J., & Li, R. (2020). Efficient allocation of customers to facilities in the multi-objective sustainable location problem. Sustainability, 12(18), 7634. DOI: https://doi.org/10.3390/su12187634
Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering, 30(4), 957–968. DOI: https://doi.org/10.1016/0360-8352(96)00045-9
Chang, P.-C., Hsieh, J.-C., & Wang, C.-Y. (2007). Adaptive multi-objective genetic algorithms for scheduling of drilling operation in printed circuit board industry. Applied Soft Computing, 7(3), 800–806.
DOI: https://doi.org/10.1016/j.asoc.2006.02.002
Foschini, L., Guns, T., et al. (2026). Anytime lexicographic enumeration of the Pareto front in multi-objective combinatorial optimisation. Journal of Multi-Criteria Decision Analysis.