.png){kind=icon}
.png){kind=icon}
Return
Complexity and approximation for scheduling problem for a torpedo
.png){kind=icon}
OA
AI
DOI：10.1016/j.cie.2011.01.015.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper considers a special case of the coupled-tasks scheduling problem on monoprocessor. The general problems were analyzed in depth by Orman and Potts (1997). In this paper, we consider that all processing times are equal to 1, the gap has exact length L, we have precedence constraints, incompatibility constraints are introduced and the criterion is to minimize the scheduling length. We use this problem to study the problem of data acquisition and data treatment of a torpedo under the water. We show that this problem is NP-complete and we propose an rho-approximation algorithm where rho <= (L+6)/6 - 1/2(L+2) + (L+3)/6n(L+2). (C) 2011 Elsevier Ltd. All rights reserved.
Keywords:
Scheduling
Coupled-tasks
Incompatibility constraints
Complexity
Approximation
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6.5
Papers:
1.0W
Citations:
3.8W