Bi-objective Makespan Scheduling Location Problem on Networks

This paper studies a bi-objective scheduling-location problem on networks, where a single machine is to be located on a graph in order to process a set of [Formula: see text] jobs placed at its vertices. Each job is subject to two possible processing-time scenarios. The problem requires simultaneously choosing the machine’s location and a job schedule so that the resulting completion times across both scenarios are Pareto-optimal. To this end, we introduce the concept of ordered regions, defined as subsets of the graph in which the order of job release dates remains invariant. We establish that within each region, the set of feasible non-dominated solutions reduces to either a singleton or a continuous interval. Building on the piecewise-linear structure of the objectives, we propose an exact algorithm that constructs and systematically prunes candidate solutions, thereby obtaining the complete Pareto front in the objective space. The proposed algorithm runs in polynomial time on general graphs, and our computational experiments indicate an empirical running-time behavior close to [Formula: see text].