Bi-objective Makespan Scheduling Location Problem on Networks
Tran Thanh Hiep et al.
What the paper says
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].
Evidence weight
Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40
| F · citation impact | 0.50 × 0.4 = 0.20 |
| M · momentum | 0.50 × 0.15 = 0.07 |
| V · venue signal | 0.50 × 0.05 = 0.03 |
| R · text relevance † | 0.50 × 0.4 = 0.20 |
† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.