Mathematical formulations and an adaptive large neighbourhood search method for the single movable machine scheduling and location problem

Abstract

Recent research has recognised the importance of jointly optimising the location and scheduling problem. However, most of them assume that machines cannot be relocated once being deployed. In contrast, practical applications can benefit from dynamically relocating machines to improve efficiency. This paper investigates a novel mobile machine scheduling challenge, where a single mobile machine is used to process a set of dispersed jobs. We need to decide when and where to locate the machine, how to allocate jobs to a proper location, and how to schedule jobs assigned to the same location upon the arrival of the machine. We present three mixed-integer linear programming (MILP) models that incorporate distinct modelling schemes and propose various valid inequalities to strengthen models. Furthermore, we develop an adaptive large neighbourhood search (ALNS) method that incorporates innovative techniques, such as a mathematical programming-based strategy to generate high-quality initial solutions, and several problem-specific destroy and repair operators. Computational experiments using random instances demonstrate the performance of the proposed ALNS. Notably, our findings demonstrate that incorporating a matheuristic method can help enhance the performance of the ALNS. Additionally, we perform a sensitivity analysis to explore the impact of varying the maximum travel distance allowed for job transportation.