zbMATH — the first resource for mathematics

Tabu search and iterated local search for the cyclic bottleneck assignment problem. (English) Zbl 1458.90445
Summary: In this paper, we study a new variant of the classical assignment problem referred to as the cyclic bottleneck assignment problem (CBAP). This problem arises in surgical and operating room (OR) scheduling and can be described as follows. Each of \(n\) successive block times can be allocated to anyone of \(n\) surgeons. The number of patients to be scheduled for surgery on a given block and the length of stay in the recovery unit of each operated patient are dependent on the type of surgery. The problem is to assign one surgeon to each OR time so as to minimize the maximum number of patients that will be expected to occupy the recovery unit in the long run. This problem has been shown to be NP-hard. Consequently, we present two algorithms that can be used to solve the problem efficiently. One algorithm is based on the Tabu search method, and the other follows an iterated local search scheme. We evaluate our algorithms on 470 benchmark instances and 470 newly generated instances, and compare them with available metaheuristics and commercial solver CPLEX. The computational results for most of our problem instances show that our proposed approaches achieve excellent performance. Our algorithms outperform existing approaches and CPLEX. The tabu search approach works slightly better than the iterated local search approach.

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI
[1] Aarts, E.; Lenstra, J. K. (Eds.), Local search in combinatorial optimization, ((1997))
[2] Bartholdi, J. J.; Orlin, J. B.; Ratliff, H. D., Cyclic scheduling via integer programms with circular one, Oper. Res., 28, 1074-1085, (1980) · Zbl 0451.90075
[3] Beckman, M.; Koopmans, T. C., Assignment problems and the location of economic activities, Econometrica, 25, 53-76, (1957) · Zbl 0098.12203
[4] Burkard, R. E., Quadratic assignment problems, Eur. J. Oper. Res., 15, 3, 283-289, (1984) · Zbl 0526.90064
[5] Burkard, R. E., Selected topics on assignment problems, Discret. Appl. Math., 123, 13, 257-302, (2002) · Zbl 1036.90056
[6] Coy, S.; Golden, B.; Runger, G.; Wasil, E., Using experimental design to find effective parameter settings for heuristics, J. Heuristics, 7, 1, 77-97, (2001) · Zbl 0967.90018
[7] Ford, D. R.; Fulkerson, D. R., Flows in networks, (1966), Princeton University Press Princeton, NJ, USA · Zbl 0139.13701
[8] Fulkerson, R.; Glicksberg, I.; Gross, O., A production line assignment problem, Technical Report RM-1102, (1953), The Rand Corporation, Sta.Monica, CA
[9] Gendreau, M.; Potvin, J. Y., Handbook of metaheuristics, (2010), Springer US · Zbl 1198.90002
[10] Gross, O., The bottleneck assignment problem, Technical Report P-1630, (1959), The Rand Corporation, Sta.Monica, CA
[11] Kuhn, H. W., The Hungarian method for the assignment problem, Naval Res. Logist. Q., 2, 83-97, (1955) · Zbl 0143.41905
[12] Kulkarni, A. J.; Baki, M. F.; Chaouch, B. A., Application of the cohort-intelligence optimization method to three selected combinatorial optimization problems, Eur. J. Oper. Res., 250, 2, 427-447, (2016) · Zbl 1346.90146
[13] Lawler, E. L., The quadratic assignment problem, Manag. Sci., 9, 4, 586-599, (1963) · Zbl 0995.90579
[14] Li, X.; Baki, F.; Tian, P.; Chaouch, B. A., A robust block-chain based tabu search algorithm for the dynamic lot sizing problem with product returns and remanufacturing, Omega, 42, 1, 75-87, (2014)
[15] Li, X.; Tian, P.; Aneja, Y., An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem, Transp. Res. Part E, 46, 6, 1111-1127, (2010)
[16] Li, X.; Wei, K.; Aneja, Y. P.; Tian, P., Design-balanced capacitated multicommodity network design with heterogeneous assets, Omega, 67, 145-159, (2017)
[17] Lourenço, H.; Martin, O.; Stützle, T., Iterated local search: framework and applications, (Gendreau, M.; Potvin, J. Y., Handbook of Metaheuristics. International Series in Operations Research & Management Science, 146, (2010), Springer US), 363-397
[18] Nelder, J. A.; Mead, R., A simplex method for function minimization, Comput. J., 7, 4, 308-313, (1965) · Zbl 0229.65053
[19] Pentico, D., Assignment problems: a Golden anniversary survey, Eur. J. Oper. Res., 176, 2, 774-793, (2007) · Zbl 1103.90060
[20] Ravindran, A.; Ramaswami, V., On the bottleneck assignment problem, J. Optim. Theory Appl., 21, 4, 451-458, (1977) · Zbl 0336.90056
[21] Ridge, E.; Kudenko, D., Tuning the performance of the MMAS heuristic, (Sttzle, T.; Birattari, M.; H. Hoos, H., Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics. Lecture Notes in Computer Science, 4638, (2007), Springer Berlin Heidelberg), 46-60
[22] Ridge, E.; Kudenko, D., Tuning an algorithm using design of experiments, (Bartz-Beielstein, T.; Chiarandini, M.; Paquete, L.; Preuss, M., Experimental Methods for the Analysis of Optimization Algorithms, (2010), Springer Berlin Heidelberg), 265-286 · Zbl 1206.68380
[23] Sahni, S.; Gonzalez, T., P-complete approximation problems, J. ACM, 23, 3, 555-565, (1976) · Zbl 0348.90152
[24] Sammarra, M.; Cordeau, J.-F.; Laporte, G.; Monaco, M. F., A tabu search heuristic for the quay crane scheduling problem, J. Sched., 10, 4, 327-336, (2007) · Zbl 1168.90468
[25] Wilcoxon, F., Individual comparisons by ranking methods, Biom. Bull., 1, 6, 80-83, (1945)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.