Task preference-based bottleneck assignment problem
Tóm tắt
The paper discusses a task preference-based bottleneck assignment problem in which there are n tasks that are divided into three phases in order of preference of performance of various tasks. The assignment problem is balanced with an equal number of agents and tasks. An agent can perform only one task and each task can be accomplished by exactly one agent. Tasks belonging to a particular phase cannot be commenced until the tasks of the previous phase have been completed. Given the performance time of each task by each agent, the aim is to find an assignment of agents to the tasks that minimize the total completion time of all tasks. The total completion time here refers to the sum of the overall completion times of three phases. An iterative algorithm for solving such a task preference-based bottleneck assignment problem is proposed in the paper. The proposed algorithm is validated with the help of theoretical results and numerical illustration. The algorithm has been coded in MATLAB and the computational results show that the algorithm performs well in terms of computing time for finding optimal assignments for task preference-based assignment problems of different sizes.
Tài liệu tham khảo
Adewumi AO, Ali MM (2010) A multi-level genetic algorithm for a multi-stage space allocation problem. Math Comput Model 51(1–2):109–26
Aggarwal V (1983) The assignment problem under categorized jobs. Eur J Oper Res 14:193–195
Aggarwal V, Tikekar VG, Hsu LF (1986) Bottleneck assignment problems under categorization. Comput Oper Res 13(1):11–26
Biermann FM, Naroditskiy V, Polukarov M, Nguyen TD, Rogers A, Jennings NR (2014) Task assignment with controlled and autonomous agents. Math Soc Sci 71:116–121
Burkard R, Dell’Amico M, Martello S (2012) Assignment problems: revised reprint. Soc Ind Appl Math
Carpenato G, Toth P (1981) Algorithm for the solution of the bottleneck assignment problem. Computing 27:179–187
Derigs U, Zimmermann U (1978) An Augmenting path method for solving linear bottleneck assignment problems. Computing 19:285–295
Dokka T, Kouvela A, Spieksma FC (2012) Approximating the multi-level bottleneck assignment problem. Oper Res Lett 40(4):282–286
Faudzi S, Abdul-Rahman S, Rahman RA (2018) An assignment problem and its application in education domain: a review and potential path. Adv Oper Res. https://doi.org/10.1155/2018/8958393
Garfinkel RS (1971) An improved algorithm for the bottleneck assignment problem. Oper Res 19:1747–1751
Hu J, Jiang Y, Zhou P, Zhang A, Zhang Q (2017) Total completion time minimization in online hierarchical scheduling of unit-size jobs. J Comb Optim 33:866–881
Ioannis P, Dimitrios GP (2020) Optimal server assignment in a two-stage tandem queueing system. Oper Res Lett 63:71–77
Jain E, Dahiya K, Sharma A, Verma V (2019) An improved algorithm for two stage time minimization assignment problem. J Comb Optim 37:713–736
Jain E, Dahiya K, Verma V (2021) Three-phase time minimization transportation problem. Eng Optim 53(3):461–473
Karademir S, Kong N, Prokopvev OA (2014) On greedy approximation algorithms for a class of two-stage stochastic assignment problems. Optim Methods Softw 29(1):42–67
Kaur P, Sharma A, Verma V, Dahiya K (2016) A priority based assignment problem. Appl Math Model 40(7):7784–7795
Kuhn HW (1955) The Hungarian method for the assignment problem. Nav Res Logist 55(2):83–97
Lahiri S (2002) Robust multivalued solutions for assignment problems: a note. Math Soc Sci 44(1):85–90
Li J, Chen J, Xin B, Dou L (2015) Solving multi-objective multi-stage weapon target assignment problem via adaptive NSGA-II and adaptive MOEA/D: A comparison study . IEEE Congress on Evolutionary Computation (CEC): 3132–3139, https://doi.org/10.1109/CEC.2015.7257280
Ortega J (2020) Multi-unit assignment under dichotomous preferences. Math Soc Sci 103:15–24
Pentico DW (2007) Assignment problems: A golden anniversary survey. Eur J Oper Res 176(2):774–793
Pferschy U (1997) Solution methods and computational investigations for the linear bottleneck assignment problem. Computing 59(3):237–258
Punnen AP (2004) On bottleneck assignment problems under categorization. Comput Oper Res. https://doi.org/10.1016/S0305-0548(02)00181-8
Punnen AP, Aneja YP (1993) Categorized assignment scheduling: a tabu search approach. J Oper Res Soc 44(7):673–679
Punnen AP, Aneja YP (2004) Lexicographic balanced optimization problems. Oper Res Lett 32(1):27–30
Rathi K, Balamohan S (2016) Two stage decision making appproach for sensor mission. RAIRO-Oper Res 50:797–807
Sonia Puri M C (2008) Two-stage time minimizing assignment problem. Omega 36(5):730–740
Volgenant A, Duin CW (2010) On a pair of job-machine assignment problems with two stages. Comput Oper Res 37:334–340
Xie F, Butt MM, Li Z (2017) A feasible flow-based iterative algorithm for the two-level hierarchical time minimization transportation problem. Comput Oper Res 86:124–139
Xie F, Sharma A, Li Z (2022) An alternate approach to solve two-level priority based assignment problem. Comput Optim Appl 2:1–44
Zhang S, Guo H, Zhu K, Yu S, Li J (2017) Multistage assignment optimization for emergency rescue teams in the disaster chain. Knowl-Based Syst 137:123–137