Task assignment under uncertainty: stochastic programming and robust optimisation approaches

Abstract

The assignment of tasks to teams is a challenging combinatorial optimisation problem. The uncertainty in the tasks’ execution processes further complicates the assignment decisions. This study investigates a variant of the typical assignment problem, in which each task can be divided into two parts, one is deterministic and the other is uncertain with respect to their workloads. From the stochastic perspective, this paper proposes both a stochastic programming model that can cope with arbitrary probability distributions of tasks’ random workload requirements, and a robust optimisation model that is applicable to situations in which limited information about probability distributions is available. An example of its application in the software project management is given. Some numerical experiments are also performed to validate the effectiveness of the proposed models and the relationships between the two models.

Keywords:

• assignment
• uncertainty
• stochastic programming
• robust optimisation

Additional information

Funding

Funding. This research is supported by National Natural Science Foundation of China [grant number 71101087], Program for Professor of Special Appointment (Eastern Scholar) at Shanghai Institutions of Higher Learning, Shanghai Shu-Guang Project [grant number 11SG40], Shanghai Pujiang Talent Program [grant number 11PJC072].