Ant colony algorithms for minimizing costs in multi-mode resource constrained project scheduling problems with spatial constraints

Abstract

This paper addresses the problem of activity scheduling and operator assignment in workstations of aerospace assembly lines. The problem is modelled as a new variant of the Multi-Mode Resource Constrained Project Scheduling Problem (MRCPSP), which incorporates practical features from aerospace workstations in assembly lines. These workstations have a substantial number of activities to be scheduled within a given assembly cycle time. It introduces particularities which are not usually addressed such as considering additional workers for performing activities, different workers’ proficiency, and spatial limitations in work zones. The objective is to schedule the activities of an aerospace workstation, minimising the total labour cost, while satisfying the cycle time and the zone’s limitations. The problem is initially formulated by employing mixed-integer linear programming methods with mathematical modelling and solved using two different algorithms: an Ant Colony System (ACS) and a memetic ACS. Given the novelty of the problem presented, new sets of benchmark cases of different sizes for this problem are also proposed and solved. To assess the performance of the algorithms, the solutions for the small-sized instances are compared in terms of deviation with the results obtained by an optimisation modelling software. Further experimentation with the algorithms is carried out with medium and large instances, showing good performance and providing reasonably good results in realistic problems.