Robust Optimization Approaches for Routing and Scheduling of Multi-Skilled Teams under Uncertain Job Skill Requirements

arXiv2009.04342MaRDI QIDQ6348754FDOQ6348754

Marc Goerigk, Yulia Anoshkina, Frank Meisel

Publication date: 9 September 2020

Abstract: We consider a combined problem of teaming and scheduling of multi-skilled employees that have to perform jobs with uncertain qualification requirements. We propose two modeling approaches that generate solutions that are robust to possible data variations. Both approaches use variants of budgeted uncertainty, where deviations in qualification requirements are bounded by a constraint. In the first approach, we aggregate uncertain constraints to ensure that the total number of job qualifications present at a job is not less than a worst-case value. We show that these values can be computed beforehand, resulting in a robust model with little additional complexity compared with the nominal model. In our second approach, we bound the overall qualification deviation over all jobs. While this approach is more complex, we show that it is still possible to derive a compact problem formulation by using a linear programming formulation for the adversarial problem based on a dynamic program. The performance of both approaches is analyzed on a test bed of instances which were originally provided for a deterministic problem version. Our experiments show the effectiveness of the proposed approaches in the presence of data uncertainty and reveal the price and gain of robustness.

This page was built for publication: Robust Optimization Approaches for Routing and Scheduling of Multi-Skilled Teams under Uncertain Job Skill Requirements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348754)