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
In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search (RBS) procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small-to medium-sized instances. For larger instances, however, this procedure requires excessive computation times, and the RBS algorithm then becomes the heuristic of choice. Journal of the Operational Research Society (2010) 61, 620-631. doi: 10.1057/jors.2008.191 Published online 18 March 2009

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
The apparent tardiness cost heuristic is one of the best performing dispatch rules for the weighted tardiness scheduling problem. This heuristic uses a lookahead parameter that has previously been set at a fixed value. We propose two different approaches for determining an appropriate value for this parameter. In the first approach, a function is used to map several instance statistics into an adequate value. The second method uses the characteristics of the current workload to determine an appropriate value each time a scheduling decision is to be made. The computational results show that the new procedures outperform the fixed value approach over a wide range of test instances and workload characteristics. The new versions are therefore suited for application in scheduling systems, since they are capable of adjusting themselves to changes in the workload, and provide important savings over the current fixed value implementations.

Abstract
In this paper, we consider the single machine earliness/tardiness scheduling problem with release dates and no unforced idle time. We analyse the performance of a varied set of heuristics. This set includes simple scheduling rules, early/tardy dispatching heuristics, a greedy procedure and a decision theory heuristic. Two different approaches are considered to calculate a lookahead parameter used in the early/tardy dispatching heuristics, and extensive experiments were performed to determine an appropriate value for this parameter. We also propose an improvement procedure that uses some dominance rules to improve the solution obtained by the heuristics. The computational results show that the use of the improvement step is recommended, since it reduces the objective function value with little additional computational effort. The best results were given by the decision theory heuristic, but this procedure is computationally expensive and therefore limited to small and medium size instances. For large instances, one of the early/tardy dispatching heuristics is then the heuristic of choice.

Abstract
In this paper, we consider the single machine scheduling problem with weighted quadratic tardiness costs. Several efficient dispatching rules are proposed. These include existing heuristics for the linear problem, as well as procedures suitably adapted to the quadratic objective function. Also, both forward and backward scheduling procedures are considered. The computational results show that the heuristics that specifically take into account the quadratic objective significantly outperform their linear counterparts. Also, the backward scheduling approach proves to be superior, and the difference in performance is even more noticeable for the harder instances. The best of the backward scheduling heuristics is both quite efficient and effective. Indeed, this procedure can quickly generate a schedule even for large instances. Also, its relative deviation from the optimum is usually rather low, and it performs adequately even for the more difficult instances.