Blazewicz, Jacek; Pawlak, Grzegorz; Tanas, Michal; Wojciechowicz, Wojciech New algorithms for coupled tasks scheduling - a survey. (English) Zbl 1262.90060 RAIRO, Oper. Res. 46, No. 4, 335-353 (2012). Summary: The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various variants of coupled tasks problems. Then, it complements previous results by providing experimental results of two new polynomial algorithms for coupled tasks scheduling, which are: an exact algorithm for \(1|(1,4,1)\), strict chains\(|C_{\max}\) problem, and a fast heuristic algorithm for more general \(1|(1,2k,1)\), strict chains\(|C_{\max}\) problem, where \(k\in \mathbb N\) . Cited in 5 Documents MSC: 90B30 Production models 90B35 Deterministic scheduling theory in operations research 90C27 Combinatorial optimization 90C59 Approximation methods and heuristics in mathematical programming 90C60 Abstract computational complexity for mathematical programming problems Keywords:coupled tasks; scheduling; complexity theory; heuristic algorithms PDFBibTeX XMLCite \textit{J. Blazewicz} et al., RAIRO, Oper. Res. 46, No. 4, 335--353 (2012; Zbl 1262.90060) Full Text: DOI Link