×

Employee workload balancing by graph partitioning. (English) Zbl 1288.05289

Summary: We consider the problem of partitioning a region into connected areas assigned to administrative officers. The employee in charge of an area takes care of all the activities which involve the towns of that area. An activity requires the effort of a subset of towns, coordinated by the employee in charge. This implies from the employee a fixed basic workload, plus a variable workload proportional to the number of towns involved. If the subset of towns associated to an activity is divided among several areas, the fixed workload is required from each of the corresponding employees, thus leading to a duplication. The problem requires to minimize duplications while balancing the workload among the employees.
The Homogeneous Areas Problem (HAP) models this situation as the search for a suitable balanced partition of a vertex-weighted and subset-weighted undirected graph into connected components. We propose a multi-commodity flow formulation, reduction procedures, a Tabu Search and a Very Large Scale Neighbourhood Search algorithm for the problem. We provide computational results for random instances and for two real-world instances, i.e. the provinces of Milan and Monza.

MSC:

05C90 Applications of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C22 Signed and weighted graphs
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

Tabu search; KaFFPa
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Orlin, J. B.; Sharma, D., Very large-scale neighborhood search, International Transactions in Operational Research, 7, 4-5, 301-317 (2000)
[2] Arora, S.; Rao, S.; Vazirani, U., Geometry, flows, and graph-partitioning algorithms, Communications of the ACM, 51, 10, 96-105 (2008)
[3] Donath, W. E.; Hoffman, A. J., Lower bounds for the partitioning of graphs, IBM Journal of Research and Development, 17, 5, 420-425 (1973) · Zbl 0259.05112
[4] Fan, N.; Pardalos, P., Linear and quadratic programming approaches for the general graph partitioning problem, Journal of Global Optimization, 48, 57-71 (2010), 10.1007/s10898-009-9520-1 · Zbl 1202.90261
[5] Ferreira, C. E.; Martin, A.; de Souza, C. C.; Weismantel, R.; Wolsey, L. A., The node capacitated graph partitioning problem: a computational study, Mathematical Programming, 81, 229-256 (1998), 10.1007/BF01581107 · Zbl 0919.90139
[6] Fjällström, P. O., Algorithms for graph partitioning: a survey, Linköping Electronic Articles in Computer and Information Science, 10 (1998)
[7] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 13, 533-549 (1986) · Zbl 0615.90083
[8] Glover, F., Ejection chains, reference structures and alternating path methods for traveling salesman problems, Discrete Applied Mathematics, 65, 1-3, 223-253 (1996) · Zbl 0846.90117
[9] Glover, F.; Hao, J.-K., The case for strategic oscillation, Annals of Operations Research, 183, 163-173 (2011) · Zbl 1214.90097
[10] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers · Zbl 0930.90083
[11] Guttmann-Beck, N.; Hassin, R., Approximation algorithms for minimum \(k\)-cut, Algorithmica, 27, 2, 198-207 (2000) · Zbl 0951.68178
[12] Kaibel, V.; Pfetsch, M., Packing and partitioning orbitopes, Mathematical Programming, 114, 1-36 (2008) · Zbl 1171.90004
[13] Kim, J.; Hwang, I.; Kim, Y.-H.; Moon, B.-R., Genetic approaches for graph partitioning: a survey, (Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO’11 (2011), ACM: ACM New York, NY, USA), 473-480
[14] Matula, David W.; Shahrokhi, Farhad, Sparsest cuts and bottlenecks in graphs, Discrete Applied Mathematics, 27, 1-2, 113-123 (1990) · Zbl 0733.05056
[15] Osipov, V.; Sanders, P.; Schulz, C., Engineering graph partitioning algorithms, (Klasing, Ralf, Experimental Algorithms. Experimental Algorithms, Lecture Notes in Computer Science, vol. 7276 (2012), Springer Berlin: Springer Berlin Heidelberg), 18-26, 10.1007/978-3-642-30850-5_3
[16] Sanders, P.; Schulz, C., Engineering multilevel graph partitioning algorithms, (Demetrescu, Camil; Halldórsson, Magnús, Algorithms—ESA 2011. Algorithms—ESA 2011, Lecture Notes in Computer Science, vol. 6942 (2011), Springer Berlin: Springer Berlin Heidelberg), 469-480, 10.1007/978-3-642-23719-5_40 · Zbl 1346.05288
[17] Thompson, P. M.; Psaraftis, H. N., Cyclic transfer algorithms for multivehicle routing and scheduling problems, Operations Research, 41, 5, 935-946 (1993) · Zbl 0797.90021
[18] Wilcoxon, F., Individual comparisons by ranking methods, Biometrics, 1, 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.