Paper Info
Title
Employee workload balancing by graph partitioning.
Abstract
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.
Year
DOI
Venue
2014
10.1016/j.dam.2013.02.014
Discrete Applied Mathematics
Keywords
Field
DocType
computational result,large scale neighbourhood search,tabu search,administrative officer,employee workload balancing,fixed basic workload,corresponding employee,connected component,homogeneous areas,fixed workload,graph partitioning,connected area
Mathematical optimization,Search algorithm,Homogeneous,Workload,Neighbourhood (mathematics),Connected component,Employee Workload,Graph partition,Mathematics,Tabu search
Journal
Volume
ISSN
Citations 
165
0166-218X
1
PageRank 
References 
Authors
0.36
13
4
Name
Order
Citations
PageRank
Alberto Ceselli134130.53
Fabio Colombo241.48
Roberto Cordone331028.87
Marco Trubian459451.20