Search

With a sharp decrease in resource utilization of the complex production process, integrated scheduling methods are urgently needed in assembly manufacturing industries. To this end, this paper presents an integrated scheduling with jobs processing and assembly sequence (ISJPAS) problem where jobs and assemblies can be processed simultaneously. As the first contribution to this work, we develop a mixed integer nonlinear programming model (MINLP) that aims at minimizing maximum completion time and determining the earliness and tardiness of jobs and resulting inventory time. The structured property of the optimal scheduling solution is analyzed with regard to job sequencing and assembly sequencing. The NP-hard nature of the problem is proved, which provides upper and lower bounds on the optimal solution. Second, an efficient discrete assembly time and arrival time control (DAATC) method is presented based on continuous time variable control models. From a modified set of benchmark problems, the proposed method is tested by comparing four assembly association levels in real applications. The comparisons indicate the potentiality of our method to satisfy the due date. Lastly, relevance of practical applications are discussed, and several future research avenues are emphasized. [ABSTRACT FROM AUTHOR]

Since most studies for estimating an angle-of-arrival (AOA) based on the antenna array have considered the antenna array with a single configuration, they are not proper to simultaneously estimate AOAs of multiple signals with various frequencies. In this paper, we introduce a cascade AOA estimation technique consisting of CAPON and Beamspace Multiple Signal Classification (MUSIC), based on a Combined Array Antenna (CAA) with Uniform Rectangular Frame Array (URFA) and Uniform Circular Array (UCA), for enhancing the above problem. In addition, we provide the computational complexity analysis for showing the low computational complexity of this technique comparing to the conventional technique.

Traveling salesman problems (TSPs) are well-known combinatorial optimization problems, and most existing algorithms are challenging for solving TSPs when their scale is large. To improve the efficiency of solving large-scale TSPs, this work presents a novel adaptive layered clustering framework with improved genetic algorithm (ALC_IGA). The primary idea behind ALC_IGA is to break down a large-scale problem into a series of small-scale problems. First, the k-means and improved genetic algorithm are used to segment the large-scale TSPs layer by layer and generate the initial solution. Then, the developed two phases simplified 2-opt algorithm is applied to further improve the quality of the initial solution. The analysis reveals that the computational complexity of the ALC_IGA is between O (n log n) and O (n 2) . The results of numerical experiments on various TSP instances indicate that, in most situations, the ALC_IGA surpasses the compared two-layered and three-layered algorithms in convergence speed, stability, and solution quality. Specifically, with parallelization, the ALC_IGA can solve instances with 2 × 10 5 nodes within 0.15 h, 1.4 × 10 6 nodes within 1 h, and 2 × 10 6 nodes in three dimensions within 1.5 h. [ABSTRACT FROM AUTHOR]

Evaluating the computational complexity of decoders is a very important aspect in the area of Error Control Coding. However, most evaluations have been performed based on hardware implementations. In this paper, different decoding algorithms for binary Turbo codes which are used in LTE standards are investigated. Based on the different mathematical operations in the diverse equations, the computational complexity is derived in terms of the number of binary logical operations. This work is important since it demonstrates the computational complexity breakdown at the binary logic level as it is not always evident to have access to hardware implementations for research purposes. Also, in contrast to comparing different Mathematical operations, comparing binary logic operations provides a standard pedestal in view to achieve a fair comparative analysis for computational complexity. The usage of the decoding method with fewer number of binary logical operations significantly reduces the computational complexity which in turn leads to a more energy efficient/power saving implementation. Results demonstrate the variation in computational complexities when using different algorithms for Turbo decoding as well as with the incorporation of Sign Difference Ratio (SDR) and Regression-based extrinsic information scaling and stopping mechanisms. When considering the conventional decoding mechanisms and streams of 16 bits in length, Method 3 uses 0.0065% more operations in total as compared to Method 1. Furthermore, Method 2 uses only 0.0035% of the total logical complexity required with Method 1. These computational complexity analysis at the binary logical level can be further used with other error correcting codes adopted in different communication standards. [ABSTRACT FROM AUTHOR]

The path towards wind power forecasting has yielded huge socio–economic benefits at a global scale. However, most of the previous studies tend to emphasize the improvement of deterministic forecasting, usually losing sight of the significance of probabilistic forecasting. In this paper, a novel forecasting system that can perform deterministic and probabilistic forecasting of wind power simultaneously, composed by the modules of feature selection, forecasting, system optimization, and system evaluation is presented to further supplement the existing studies in this field. Concretely, a hybrid feature selection strategy is proposed in the feature selection module to determine optimal system input; superior to traditional gradient descent algorithm, a dynamic reservoir theory-based recurrent neural network is developed in the forecasting module; an enhanced multi-objective optimization algorithm with the objectives of accuracy and stability is proposed in the system optimization module to provide an optimal scenario for system parameters; the effectiveness and feasibility of the proposed system is then validated in the evaluation module. Moreover, the comprehensive performance analysis of the proposed system is investigated in depth. Finally, the experimental results demonstrate that the proposed system has a significant advantage over the benchmarks considered, further verifying its tremendous potential to be used in a practical wind power system. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of the time complexity of algorithms prepared for solving heat transfer problems at nanoscale. The first algorithm uses the classic Dual-Phase-Lag model, whereas the second algorithm employs a reduced version of the model obtained using a Krylov subspace method. This manuscript includes a description of the finite difference method approximation prepared for analysis of the real microelectromechanical system (MEMS) structure manufactured by the Polish Institute of Electron Technology. In addition, an approximation scheme of the model, as well as the Krylov subspace-based model order reduction technique are also described. The paper considers simulation results obtained using both investigated versions of the Dual-Phase-Lag model. Moreover, the relative error generated by the reduced model, as well as the computational complexity of both algorithms, and a convergence of the proposed approach are analyzed. Finally, all analyses are discussed in detail.

This work analyses the discrete solution of Hughes‐Hartogs (HH) for the transmission rate maximisation problem with power constraint in the orthogonal frequency division multiplexing access (OFDMA) systems and explores mechanisms to reduce the computational complexity of greedy algorithms. In addition to the solution characterisation, a computational complexity analysis is developed, considering the number of executed operations for running time purpose. Moreover, the authors have compared the system capacity via the throughput obtained with the HH solution, and its variants combined with three complexity reduction mechanisms. These tools consist of an initial allocation bit vector calculated by rounding the results of the water‐filling (WF) solution, the multiple subchannels per iteration updating and the adoption of a subchannel grouping procedure. Their findings indicate that the update of multiple subchannels and the subcarriers grouping techniques reduce the number of iterations required for convergence of the original HH, with some throughput degradation. Also, the bit‐allocation mechanism based on the WF is deployed as an alternative to overcome the HH solution, increasing the computational complexity. [ABSTRACT FROM AUTHOR]

Given a task that requires some skills and a social network of individuals with different skills, the Team Formation problem asks to find a team of individuals that together can perform the task, while minimizing communication costs. Since the problem is NP-hard, we identify the source of intractability by analyzing its parameterized complexity with respect to parameters such as the total number of skills k , the team size l , the communication cost budget b , and the maximum vertex degree Δ. We show that the computational complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph formed by the selected team, we obtain fixed-parameter tractability for example with respect to the parameter k . In contrast, when using the diameter as measure, the problem is intractable with respect to any single parameter; however, combining Δ with either b or l yields fixed-parameter tractability. [ABSTRACT FROM AUTHOR]

Turbo codes apply an iterative message passing mechanism between two concatenated decoders. Their astounding performance has led to their widespread adoption in several communication standards such as Long Term Evolution, and Code Division for Multiple Access 2000. This paper gives an overview of three bit-level decoding Max-Log-MAP algorithms with Sign Difference Ratio-based early stopping that can be used with Long Term Evolution Turbo Codes. A detailed computational complexity analysis is given for the three methods. It is observed that the complexity of the decoding methods decrease significantly as the Eb/N0 increases when Sign Difference Ratio is used. Moreover, the Bit Error Rate performance of the methods was also assessed and compared for different modulation schemes. Results show that the different methods perform differently in the waterfall and error-floor regions with different modulation schemes. Moreover, the computational complexity analysis show that Method 2 requires fewer overall number of computations compared to Methods 1 and 3. [ABSTRACT FROM AUTHOR]

In this study, the authors introduce a novel hybrid cooperative localisation scheme when both distance and angle measurements are available. Two linear least squares (LLS) hybrid cooperative schemes based on angle of arrival–time of arrival (AoA–ToA) and AoA–received signal strength (AoA–RSS) signals are proposed. The proposed algorithms are modified to accommodate cooperative localisation in resource constrained networks where only distance measurements are available between target sensors (TSs) while both distance and angle measurements are available between reference sensors and TSs. Furthermore, an optimised version of the LLS estimator is proposed to further enhance the localisation performance. Moreover, localisation of sensor nodes in networks with limited connectivity (partially connected networks) is also investigated. Finally, computational complexity analysis of the proposed algorithms is presented. Through simulation, the superior performance of the proposed algorithms over its non‐cooperative counterpart and the hybrid signal based iterative non‐linear least squares algorithms is demonstrated. [ABSTRACT FROM AUTHOR]

In this study, the authors study the problem of smart meter deployment optimisation for appliance load monitoring, that is, to monitor a number of devices without any ambiguity using the minimum number of low-cost smart meters. The importance of this problem is due to the fact that the number of meters should be reduced to decrease the deployment cost, improve reliability and decrease congestion. In this way, in future, smart meters can provide additional information about the type and number of distinct devices connected, besides their normal functionalities concerned with providing overall energy measurements and their communication. The authors present two exact smart meter deployment optimisation algorithms, one based on exhaustive search and the other based on efficient implementation of the exhaustive search. They formulate the problem mathematically and present computational complexity analysis of their algorithms. Simulation scenarios show that for a typical number of home appliances, the efficient search method is significantly faster compared to the exhaustive search and can provide the same optimal solution. The authors also show the dependency of their method on the distribution of the load pattern that can potentially be in a typical household.

In this paper, novel knowledge‐aided space‐time adaptive processing (KA‐STAP) algorithms using sparse representation/recovery (SR) techniques by exploiting the spatio‐temporal sparsity are proposed to suppress the clutter for airborne pulsed Doppler radar. The proposed algorithms are not simple combinations of KA and SR techniques. Unlike the existing sparsity‐based STAP algorithms, they reduce the dimension of the sparse signal by using prior knowledge resulting in a lower computational complexity. Different from the KA parametric covariance estimation (KAPE) scheme, they estimate the covariance matrix using SR techniques that avoids complex selections of the Doppler shift and the covariance matrix taper. The details of the selection of potential clutter array manifold vectors according to prior knowledge are discussed and compared with the KAPE scheme. Moreover, the implementation issues and the computational complexity analysis for the proposed algorithms are also considered. Simulation results show that our proposed algorithms obtain a better performance and a lower complexity compared with the sparsity‐based STAP algorithms and outperform the KAPE scheme in presence of errors in prior knowledge. [ABSTRACT FROM AUTHOR]

The authors apply two approaches to reduce the computation time of the residual complexity similarity metric employed in image registration applications aimed at hardware‐based implementations with low‐complexity transforms. First, the similarity metric is computed in image sub‐blocks, which are subsequently combined into a global metric value. Second, the discrete cosine transform (DCT) needed in the computation of the similarity measure is replaced with multiplier‐free low‐complexity approximate transforms. The authors propose a new low‐complexity transform requiring only 18 additions in an 8 × 8 block and compare it to: the round DCT, the signed DCT, the Hadamard transform and the Walsh‐Hadamard transform. Detailed computational complexity analysis reveals that block‐wise processing alone reduces computational cost by a factor of 8‐9 for original DCT composed of multiplications and additions, and up to ≃4.90 when the proposed DCT is utilised; being the computation performed with additions only. Results obtained from computer simulated and realistic X‐ray images demonstrate block‐wise processing and approximate transforms result in successful image registration, making residual complexity similarity measure available to hardware‐accelerated fast image registration applications. [ABSTRACT FROM AUTHOR]

We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios, such as gerrymandering in political districting or work balancing in an online situation. The central aspect of our model is the deletion of certain vertices and the redistribution of their load to neighboring vertices in a completely balanced way. We investigate how the underlying graph structure, the knowledge of which vertices should be deleted, and the relation between old and new vertex loads influence the computational complexity of the underlying graph problems. Our results establish a clear borderline between tractable and intractable cases. [ABSTRACT FROM AUTHOR]

In the distributed video coding (DVC) context, predictive Intra coding plays an important role not only as one of the most meaningful (low encoding complexity) benchmarks but also as the adopted coding mode for the so-called key frames used in the most popular DVC architectures. While the first DVC codecs adopted the H.263 Intra codec to play this role, it became clear around 2005 that the (standard) Intra coding reference codec had evolved and should become the H.264/AVC Intra codec, which has been used since then by the DVC literature. However, while DVC solutions have been evolving since those times, also predictive video coding has evolved and a new predictive video coding standard has recently emerged, the High Efficiency Video Coding (HEVC) standard. To acknowledge this evolution and be fair with the predictive coding technology, the improved DVC solutions should now integrate and be compared with the improved and more relevant HEVC standard and not anymore with the H.264/AVC 10-year-old standard. In this context, this paper proposes to upgrade the DVC tools and benchmarking by adopting the HEVC Intra codec to take the role that the H.264/AVC Intra standard was previously playing. To assess the impact of this inevitable upgrade, an advanced, representative DVC solution has been adopted and its performance assessed and compared in the context of the H.264/AVC and HEVC standard frameworks. The compression efficiency and computational complexity experiments performed allow concluding that upgrading DVC solutions with HEVC Intra coding allows strengthening the DVC positioning in the video coding landscape. This conclusion highlights how the experiments performed in this paper are critical to define the new DVC status quo . [ABSTRACT FROM AUTHOR]

In this study, a novel sparsity‐based space–time adaptive processing algorithm based on the complex‐valued Homotopy technique is proposed for airborne radar applications. The proposed algorithm firstly extends the existing standard real‐valued Homotopy method to a more general complex‐valued application using the gradient approaches. By exploiting the sparsity of the clutter spectrum in the whole spatiotemporal plane, the proposed algorithm recovers the clutter spectrum via the proposed complex Homotopy algorithm and then uses it to estimate the clutter covariance matrix, followed by the space–time filtering and the target detection. Furthermore, the implementations of the proposed algorithm are detailed. The computational complexity analysis shows that the proposed algorithm has a lower‐computational complexity than the existing complex‐valued Homotopy algorithm. Simulation results show that the proposed algorithm converges at a very fast speed (only 4–6 snapshots in the authors simulations) and provides both excellent detection performance and easy parameter settings. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates the gene selection problem for microarray data with small samples and variant correlation. Most existing algorithms usually require expensive computational effort, especially under thousands of gene conditions. The main objective of this paper is to effectively select the most informative genes from microarray data, while making the computational expenses affordable. This is achieved by proposing a novel forward gene selection algorithm (FGSA). To overcome the small samples' problem, the augmented data technique is firstly employed to produce an augmented data set. Taking inspiration from other gene selection methods, the L 2-norm penalty is then introduced into the recently proposed fast regression algorithm to achieve the group selection ability. Finally, by defining a proper regression context, the proposed method can be fast implemented in the software, which significantly reduces computational burden. Both computational complexity analysis and simulation results confirm the effectiveness of the proposed algorithm in comparison with other approaches. [Copyright &y& Elsevier]

This article deals with multicriteria optimization models and algorithms of movement scheduling for many objects to synchronize their movement (2CMSS problem). The model consists of two parts: (1) node–disjoint path planning visiting specified nodes for K objects with a given vector of intermediate nodes for each one (NDSP problem); (2) movement synchronization in some intermediate nodes (MS problem). For synchronous movement, two categories of criteria are defined: time of movement and ‘distance’ of K-moved objects from the movement pattern. We defined the problem as a discrete-continuous, non-linear, two-criteria mathematical programming problem. We proposed to use a two-stage algorithm to solve the 2CMSS problem (as lexicographic solution): At first we have to find the vector of node–disjoint shortest paths for K objects visiting intermediate nodes to set optimal paths under the assumption that we use maximal possible velocities on each arc belonging to a path for each object (solution of the NDSP problem), and next we try to decrease the values of velocities to optimize the second criterion (synchronization, solution of the MS problem). Experimental analyses of effectiveness and complexity of the algorithms are presented. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates the center selection of multi-output radial basis function (RBF) networks, and a multi-output fast recursive algorithm (MFRA) is proposed. This method can not only reveal the significance of each candidate center based on the reduction in the trace of the error covariance matrix, but also can estimate the network weights simultaneously using a back substitution approach. The main contribution is that the center selection procedure and the weight estimation are performed within a well-defined regression context, leading to a significantly reduced computational complexity. The efficiency of the algorithm is confirmed by a computational complexity analysis, and simulation results demonstrate its effectiveness. [Copyright &y& Elsevier]

Abstract: The Steiner Forest Problem (SFP for short) is a natural generalization of the classical Steiner Tree Problem. Instead of only one terminal net there is given a set of terminal nets that have to be connected by choosing edges at minimum cost. Richey and Parker [M.B. Richey, R.G. Parker, On multiple Steiner subgraph problems, Networks 16 (4) (1986) 423–438] posed the question whether SFP is hard on series-parallel graphs. We partially answer this question by showing that SFP is strongly -hard on graphs with treewidth 3. On the other hand, a quadratic time algorithm for the special case on outerplanar graphs is suggested. Since series-parallel graphs have treewidth 2 and outerplanar graphs are series-parallel, we almost close the gap between polynomially solvable and hard cases. [Copyright &y& Elsevier]

This paper proposes a novel hybrid forward algorithm (HFA) for the construction of radial basis function (RBF) neural networks with tunable nodes. The main objective is to efficiently and effectively produce a parsimonious RBF neural network that generalizes well. In this study, it is achieved through simultaneous network structure determination and parameter optimization on the continuous parameter space. This is a mixed integer hard problem and the proposed HFA tackles this problem using an integrated analytic framework, leading to significantly improved network performance and reduced memory usage for the network construction. The computational complexity analysis confirms the efficiency of the proposed algorithm, and the simulation results demonstrate its effectiveness. [ABSTRACT FROM AUTHOR]

A new algorithm for reducing the division operation to a series of smaller divisions is introduced. Partitioning the dividend into segments, we perform divisions, shifts, and accumulations taking into account the weight of dividend bits. Each partial division can be performed by any existing division algorithm. From an algorithmic point of view, computation analysis is performed in comparison with the existing algorithms. From an implementation point of view, since the division can be performed by any existing divider, the designer can choose the divider which best meets his specifications. Although the algorithm is presented for integer numbers, it can be easily generalized for fractions, since it is only a matter of representation. Two possible implementations of the algorithm, namely the sequential and parallel are derived, with several variations, allowing performance, cost, and cost/performance trade-offs. Exhaustive comparisons of the derived implementations with many existing implementations in terms of area cost, performance, and cost/performance are done. A plethora of alternative implementations can be derived due to a variable number of partitions. [ABSTRACT FROM AUTHOR]

This paper describes the automated complexity analysis (ACA) system for automated higher-order complexity analysis of functional programs synthesized with the NUPRL proof development system. We introduce a general framework for defining models of computational complexity for functional programs based on an annotation of a given operational language semantics. Within this framework, we use type decomposition and polynomialization to express the complexity of higher-order terms. Symbolic interpretation of open terms automates complexity analysis, which involves generating and solving higher-order recurrence equations. Finally, the use of the ACA system is demonstrated by analyzing three different implementations of the pigeonhole principle. [Copyright &y& Elsevier]

This paper presents an analysis of the time complexity of algorithms prepared for solving heat transfer problems at nanoscale. The first algorithm uses the classic Dual-Phase-Lag model, whereas the second algorithm employs a reduced version of the model obtained using a Krylov subspace method. This manuscript includes a description of the finite difference method approximation prepared for analysis of the real microelectromechanical system (MEMS) structure manufactured by the Polish Institute of Electron Technology. In addition, an approximation scheme of the model, as well as the Krylov subspace-based model order reduction technique are also described. The paper considers simulation results obtained using both investigated versions of the Dual-Phase-Lag model. Moreover, the relative error generated by the reduced model, as well as the computational complexity of both algorithms, and a convergence of the proposed approach are analyzed. Finally, all analyses are discussed in detail. [ABSTRACT FROM AUTHOR]