Abstract
In this paper, we consider the single machine earliness/tardiness scheduling problem with no idle time. Two of the lower bounds previously developed for this problem are based on Lagrangean relaxation and the multiplier adjustment method, and require an initial sequence. We investigate the sensitivity of the lower bounds to the initial sequence, and experiment with different dispatch rules and some dominance conditions. The computational results show that it is possible to obtain improved lower bounds by using a better initial sequence. The lower bounds are also incorporated in a branch-and-bound algorithm, and the computational tests show that one of the new lower bounds has the best performance for larger instances.

Abstract
This paper presents several beam search algorithms for the single-machine earliness/tardiness scheduling problem with release dates and no unforced idle time. These algorithms include classical beam search procedures, with both priority and total cost evaluation functions, as well as the filtered and recovering variants. Both priority evaluation functions and problem-specific properties were considered for the filtering step used in the filtered and recovering procedures. The computational results show that the recovering beam search algorithms outperform their filtered counterparts, while the priority-based filtering procedure proves superior to the rules-based alternative. The beam search procedure with a total cost function provides very good results but is computationally expensive. The recovering algorithm is quite close in solution quality and is significantly faster, so it can be used to solve even large instances.

Abstract
In this paper, we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into weighted earliness and weighted tardiness subproblems. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is the sum of the lower bounds for the two subproblems. The lower bounds and several version, of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.

Abstract
A dispatch rule and a greedy procedure are presented for the single machine earliness/tardiness scheduling problem with no idle time and compared with the best of the existing dispatch rules. Both dispatch rules use a lookahead parameter that had previously been set at a fixed value. We develop functions that map some instance statistics into appropriate values for that parameter. We also consider the use of dominance rules to improve the solutions obtained by the heuristics. The computational results show that the function-based versions of the heuristics outperform their fixed value counterparts and that the use of the dominance rules can indeed improve solution quality with little additional computational effort.

Abstract
In this paper, we present filtered and recovering beam search algorithms for the single machine earliness/tardiness scheduling problem with no idle time, and compare them with existing neighbourhood search and dispatch rule heuristics. Filtering procedures using both priority evaluation functions and problem-specific properties have been considered. The computational results show that the recovering beam search algorithms outperform their filtered counterparts, while the priority-based filtering procedure proves superior to the rules-based alternative. The best solutions are given by the neighbourhood search algorithm, but this procedure is computationally intensive and can only be applied to small or medium size instances. The recovering beam search heuristic provides results that are close in solution quality and is significantly faster, so it can be used to solve even large problems.

Abstract
We tackle the problem of sequence classification using relevant subsequences found in a dataset of protein labelled sequences. A subsequence is relevant if it is frequent and has a minimal length. For each query sequence a vector of features is obtained. The features consist in the number and average length of the relevant subsequences shared with each of the protein families. Classification is performed by combining these features in a Bayes Classifier. The combination of these characteristics results in a multi-class and multi-domain method that is exempt of data transformation and background knowledge. We illustrate the performance of our method using three collections of protein datasets. The performed tests showed that the method has an equivalent performance to state of the art methods in protein classification.