An evolutionary algorithm for joint bi-criteria location-scheduling problem

A new case of joint location and scheduling (ScheLoc) problem is considered. It deals with selecting a non-fixed number of locations for identical parallel executors (machines) from a given set of available sites. Simultaneously, a schedule for a set of tasks is sought. For every task, it comprises an executor carrying-out the task and the moment of time when the performance of the task is started. The locations for executors and the schedule are evaluated by two criteria: the sum of task completion times and investment costs incurred when locations for executors are selected and launched. It is justified that the joint optimization problem is strongly NP-hard. In consequence, a heuristic algorithm Alg BC is proposed, which uses the general scheme of NSGA II provided for the multi-criteria optimization. The performance of Alg BC is evaluated for small instances by exact solutions determined by the Matlab solver. The sensitivity analysis for bigger instances is also provided, which among others, allows examining the influence of both component criteria on results generated by the evaluated algorithm. A case study dealing with the evacuation of citizen groups from danger zones is provided as an example of the investigated bi-criteria ScheLoc problem. The usefulness of Alg BC is confirmed as well. (C) 2021 by the authors; licensee Growing Science, Canada

Automated summary

This study considers a joint location and scheduling problem involving selecting a number of executor locations and task plans. A heuristic algorithm Alg BC is proposed, utilizing the NSGA II scheme for multi-objective optimization. The performance of Alg BC is evaluated for small instances, and sensitivity analysis is provided for larger instances.