.png){kind=icon}
Return
Approximation Algorithms on a Scheduling Problem with Connectivity Constraints
.png){kind=icon}
PRE
AI
DOI：10.1142/s0129054126490043.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We propose a novel scheduling problem with connectivity constraints. This problem defines a connected graph G = (V,E), where each edge e is an element of E is associated with a processing time t(e) and cost c(e), i.e., t,c : E -> & Ropf;(+) boolean OR{0}, where & Ropf;(+) is the set of real positive numbers. The objective is to select a path P in G to establish connectivity between two given vertices and further to schedule the corresponding edges on m 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.
Keywords:
Scheduling
connectivity constraints
approximation algorithm
uniform machines
Journal
I
IF:
0.6
Papers:
51
Citations:
0
Organization
Cited Papers
No cited papers available