Abstract
In this paper, we consider the single machine earliness/tardiness scheduling problem with job-independent penalties, and no machine idle time. Several dispatching heuristics are proposed, and their performance is analysed on a wide range of instances. The heuristics include simple scheduling rules, as well as a procedure that takes advantage of the strengths of each of those rules. We also consider early/tardy dispatching procedures, and a heuristic method based on existing adjacent precedence conditions. An improvement procedure that can be used to improve the schedules generated by the heuristics is also proposed. The computational tests show that the best results are given by the early/tardy dispatching rules. These heuristics are also quite fast, and are capable of quickly solving even very large instances. The use of the improvement procedure is recommended, since it improves the solution quality, with little additional computational effort.

Abstract
In this paper, we present dominance conditions for the single machine weighted earliness scheduling problem with no idle time. We also propose an algorithm that can be used to improve upper bounds for the weighted earliness criterion and lower bounds for an earliness/tardiness problem. The computational tests show that the algorithm is superior to an initial heuristic schedule and an existing adjacency condition.

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
In this paper we present three hybrid heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. Our heuristic is a combination of a steady-state genetic algorithm and three improvement procedures. The two computationally less expensive of these three improvement procedures are used inside the genetic algorithm to improve the schedule obtained after the application of genetic operators, whereas the more expensive one is used to improve the best solution returned by the genetic algorithm. We have compared our hybrid approaches against existing recovering beam search and genetic algorithms. The computational results show the effectiveness of our hybrid approaches. Indeed, our hybrid approaches outperformed the existing heuristics in terms of solution quality as well as running time.

Abstract
In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose a genetic approach based on a random key alphabet and present several algorithms based on this approach. These versions differ on the generation of both the initial population and the individuals added in the migration step, as well as on the use of local search. The proposed procedures are compared with the best existing heuristics, as well as with optimal solutions for the smaller instance sizes. The computational results show that the proposed algorithms clearly outperform the existing procedures and are quite close to the optimum. The improvement over the existing heuristics increases with both the difficulty and the size of the instances. The performance of the proposed genetic approach is improved by the initialization of the initial population, the generation of greedy randomized solutions, and the addition of the local search procedure. Indeed, the more sophisticated versions can obtain similar or better solutions and are much faster. The genetic version that incorporates all the considered features is the new heuristic of choice for small and medium size instances.

Abstract
In this paper, we present greedy randomised dispatching heuristics for the single-machine scheduling problem with quadratic earliness and tardiness costs and no machine idle time. The several heuristic versions differ, on the one hand, on the strategies involved in the construction of the greedy randomised schedules. On the other hand, these versions also differ on whether they employ only a final improvement step or perform a local search after each greedy randomised construction. The proposed heuristics were compared with existing procedures as well as with optimum solutions for some instance sizes. The computational results show that the proposed procedures clearly outperform their underlying dispatching heuristic, and the best of these procedures provide results that are quite close to the optimum. The best of the proposed algorithms is the new recommended heuristic for large instances as well as a suitable alternative to the best existing procedure for the larger of the middle-sized instances.