The multi-skilled multi-period workforce assignment problem

Seasonal business operations hire workers depending on environmental conditions and market prices. For example, during the growing and harvest seasons, agricultural businesses employ multiple workers to perform activities such as tilling soil, sowing seed, spreading fertiliser, spraying pesticides, removing weeds, and threshing crops. This study proposes two mixed-integer programming (MIP) models with an effective heuristic to solve the problem of simultaneously assigning multiple multi-skilled workers to the numerous tasks that require different skill sets during single-and multiple-period operations. The multi-skilled workforce management (MSWM) problem is NP hard in the strong sense, and it seems unlikely that large-sized realistic instances could be solved efficiently by exact algorithms directly except for some instances with very sparse tasks and skill sets. Thus, this study presents a heuristic algorithm using k-Opt as a diversification strategy embedded within the Tabu search for this complex problem. To assess the solution quality of the k-Opt heuristic, we solved two sets of instances with different sizes by running the exact solver Gurobi and the proposed heuristic algorithm with a single processor as well as running Gurobi with multiple processors. This heuristic is applicable to other multitasking situations where many workers with multiple capabilities are deployed.