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.