Abstract
This paper considers a problem in which there is a set of jobs to be sequenced on a single machine. Each job has a weight and the objective is to sequence the jobs to minimize total weighted squared tardiness. A branch-and-bound algorithm is developed for optimally solving the problem. Several dominance conditions are presented for possible inclusion in the branch-and-bound algorithm. The dominance conditions are included in the branch-and-bound algorithm, which is tested on randomly generated problems of various numbers of jobs, due date tightness and due date ranges. The results show that the dominance conditions dramatically improve the efficiency of the branch-and-bound algorithm.

Abstract
In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule. The computational experiments show that the best results are provided by the heuristics that explicitly consider both early and tardy costs, and the quadratic objective function. Therefore, it is indeed important to specifically address the quadratic feature of the cost function, instead of simply using procedures originally developed for a linear objective function. The heuristics are quite fast, and are capable of quickly solving even very large instances. The use of an improvement step is recommended, since it usually improves the solution quality with little additional computational effort.

Abstract
In this paper, we consider the single machine weighted tardiness scheduling problem with sequence-dependent setups. We present heuristic algorithms based on the beam search technique. These algorithms include classic beam search procedures, as well as the filtered and recovering variants. Previous beam search implementations use fixed beam and filter widths. We consider the usual fixed width algorithms, and develop new versions that use variable beam and filter widths. The computational results show that the beam search versions with a variable width are marginally superior to their fixed value counterparts, even when a lower average number of beam and filter nodes is used. The best results are given by the recovering beam search algorithms. For large problems, however, these procedures require excessive computation times. The priority beam search algorithms are much faster, and can therefore be used for the largest 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 beam search heuristics for the single machine early/tardy scheduling problem with job-independent penalties, and no machine idle time. These heuristics include priority and detailed classic beam search algorithms, as well as filtered and recovering procedures. Three dispatching rules are considered as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search heuristics. The computational results show that the performance of the beam search procedures does improve with the quality of the dispatching rule. The detailed and recovering algorithms clearly Outperform the best existing heuristic, and the improvement is particularly higher for the more difficult instances. The detailed beam search algorithm provides the best performance, and is recommended for small to medium size instances. For larger instances, however, this algorithm requires excessive computation times. The recovering beam search procedure is computationally more efficient, and is then the heuristic of choice for medium to large instances.