From a Multi-Skilled Staff-Scheduling Problem to the Mixed Set Covering, Packing and Partitioning Polytope

This thesis is divided into two parts: Multi-Skilled Staff-Scheduling Problem and a polyhedral study on the Mixed Set Covering, Packing and Partitioning Problem, where the first part is a motivating example of the latter.;In the multi-skilled staff-scheduling problem, we study the problem of scheduling customer service agents at an international terminal of a large airport. The staff members are heterogeneous with different skills and skill levels. The skill specification is two-dimensional, defined by operational skills and language proficiency. In the mathematical model, we also consider the scheduling of meal and rest breaks, and multiple locations. The problem is shown to be NP-hard. We derive valid inequalities to speed up the computational procedure. With our mathematical model, we are able to help schedule planners make decisions and examine the impacts of different types of flexibility on the level of service provided. Our model can also help decision makers with long-term work-schedule planning.;Motivated by the staff-scheduling problem, the second part of this thesis studies the polyhedral structure of the mixed set covering, packing and partitioning problem, i.e., a problem that contains set covering, set packing and set partitioning constraints. We first study the mixed odd hole polytope, which is the polytope associated with a mixed odd hole consisting of covering and packing "edges". Adopting a graphical approach and considering the "interactions" between the different types of inequalities, we derive the mixed odd hole inequality, thereby completely characterizing the mixed odd hole polytope. We then generalize the mixed odd hole inequality for the general mixed covering and packing polytope. Computational results show that the mixed odd hole inequalities are helpful in reducing solution time. We also provide examples of problem settings in which the inequalities can be used to help decision making.