Solving large scale office scheduling problems as combinatorial auctioning problems

MEng (Industrial Engineering), North-West University, Potchefstroom CampusWithin specific exible work models, employees must reserve an office to gain access to one. However, over-bookings and double-bookings arise with such approaches. This can result in the inefficient utilisation of the available office space and impede productivity. This study presents an auctioning approach as an alternative to the reservation approach most often used in exible work models. The aim is to increase office capacity by improving the utilisation of available office spaces. The problem of allocating employees to offices is known within the realm of operations research as the office space allocation problem (OSA). Using an auctioning approach, this study proposes to construct office schedules by determining the winners in an office timeslot auction. Determining which employee will receive which timeslot in the auction can be modelled as a well-known optimisation problem referred to as the winner determination problem (WDP). This problem is often found in combinatorial auctions(CA), where bidders can bid on sets of discrete items. This study, therefore, seeks to model the OSA problem in exible work models as a CA where employees are required to bid on sets of timeslots to receive access to an office. Office schedules are then constructed by solving the WDP problem. This problem is referred to as the OSA-CA problem. This study presents three problem-solving approaches to solve the OSA-CA problem. The first two problem-solving approaches are binary integer linear programming (BILP) models that represent different formulations of the OSA-CA problem. The third problem-solving approach is a heuristic algorithm. Analyses on each problem-solving approach are completed using data generated from an algorithm that produces OSA-CA problem instances. These analyses are constructed to verify the feasibility of each problem-solving approach and validate and compare their performance. The verification analyses prove that each problem-solving approach can obtain feasible solutions for OSA-CA problems. These analyses also show that the heuristic algorithm can obtain optimal solutions when presented with an OSA-CA problem where the ratio of employees to offices is less than 3:1. To accurately represent the heuristic algorithm's performance relative to the two BILP models', problem instances need to have a ratio of employees to offices of at least 3:1, respectively. The validation analyses show that the two BILP models can obtain better quality final solutions than the heuristic algorithm. However, the heuristic algorithm can obtain better quality solutions for initial solutions. The heuristic algorithm can also obtain solutions at a significantly faster rate than the two BILP models, irrespective of the scale of the problem.Master