Approximation Algorithms on a Scheduling Problem with Connectivity Constraints

We propose a novel scheduling problem with connectivity constraints. This problem defines a connected graph [Formula: see text], where each edge [Formula: see text] is associated with a processing time [Formula: see text] and cost [Formula: see text], i.e., [Formula: see text], where [Formula: see text] is the set of real positive numbers. The objective is to select a path [Formula: see text] in [Formula: see text] to establish connectivity between two given vertices and further to schedule the corresponding edges on [Formula: see text] parallel machines for minimizing the sum of the makespan and the total cost. This problem is strongly NP-hard, combining elements of graph theory and parallel machine scheduling. In this paper, we focus on the uniform parallel machine environment, for which we develop approximation algorithms and provide worst-case analysis. Our results contribute to scheduling theory in combinatorial optimization and provide new insights into network restoration under resource constraints.