Integrated workforce assignment in identical parallel machine scheduling with compressible setup times

In this paper we present a problem of scheduling identical parallel processes with setup times dependent on workforce assignment. The objective is to minimize the workforce requirement in meeting a specified production demand. The problem considered has many practical applications, such as assigning gig workers to customer deliveries, in large scale baking operations in the confectionary industry, printing presses operating multiple identical printers, agent-assisted automated kiosks in service centers, etc. We present a case study of a production unit dealing with the assignment of temporary workforce to setting up baking processes across multiple identical ovens in malt-based beverage mix production. We present an integer programming formulation for the problem and a novel constraint programming formulation. We prove that this problem is NP-hard. To solve real-size problem instances, we propose a decomposition strategy to split the problem into two parts- machine scheduling aimed at minimizing the required workforce size followed by a satisfiability problem assigning workforce to the pre-scheduled tasks. Consequently, a three-step solution heuristic based on a combination of mathematical programming and constraint programming is developed. Analysis related to the impact of required capacity utilization on workforce size and worker utilization, relationship of the target objective with the objective of makespan minimization and the impact of break policies on the stated objective and worker utilization level are presented to generate insights.