Abstract
In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs. and no machine idle time. We propose a genetic approach based on a random key alphabet. Several genetic algorithms based on this approach are presented. These versions differ on the generation of the initial population, as well as on the use of local search. The proposed procedures are compared with existing heuristics, as well as with optimal solutions for the smaller instance sizes. The computational results show that the performance of the proposed genetic approach is improved by the addition of a local search procedure, as well as by the insertion of simple heuristic solutions in the initial population. Indeed, the genetic versions that include either or both of these features not only provide significantly better results, but are also much faster. The genetic versions that use local search are clearly superior to the existing heuristics, and the improvement in performance over the best existing procedure increases with both the size and difficulty of the instances. These genetic procedures are also quite close to the optimum, and provided an optimal solution for most of the test instances.

Abstract
In this paper, we present a hybrid genetic algorithm for a version of the early/tardy scheduling problem in which no unforced idle time may be inserted in a sequence. The chromosome representation of the problem is based on random keys. The genetic algorithm is used to establish the order in which the jobs are initially scheduled, and a local search procedure is subsequently applied to detect possible improvements. The approach is tested on a set of randomly generated problems and compared with existing efficient heuristic procedures based on dispatch rules and local search. The computational results show that this new approach, although requiring slightly longer computational times, is better than the previous algorithms in terms of solution quality.

Abstract
In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. We propose a lower bounding procedure based on the relaxation of the jobs' completion times. Optimal branch-and-bound algorithms are then presented. These algorithms incorporate the proposed lower bound, as well as an insertion-based dominance test. The branch-and-bound procedures are tested on a wide set of randomly generated problems. The computational results show that the branch-and-bound algorithms are capable of optimally solving, within reasonable computation times, instances with up to 20 jobs.

Abstract
In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. 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. Several dispatching rules are considered as evaluation functions, to analyze the effect of different rules on the effectiveness of the beam search algorithms. The computational results show that using better rules improves the performance of the beam search heuristics. The detailed, filtered beam search (FBS) and recovering beam search (RBS) procedures outperform the best existing heuristic. The best results are given by the recovering and detailed variants, which provide objective function values that are quite close to the optimum. For small to medium size instances, either of these procedures can be used. For larger instances, the detailed beam search (DBS) algorithm requires excessive computation times, and the RBS procedure then becomes the heuristic of choice.

Abstract
This paper considers the single machine scheduling problem with linear earliness and quadratic tardiness costs. The research on the version with an inserted idle time focused on an exact approach, while several heuristics were already proposed for the version with no idle time. These heuristics were then the basis for the development of new heuristic procedures for the version with idle time. Some improvement procedures were also considered. The new heuristics outperformed the existing procedures. A genetic algorithm provides the best results in terms Of Solution quality, but is computationally intensive. One of the backward scheduling dispatching rules provides results of similar quality and can quickly solve even large instances. The new heuristics were also applied, with the appropriate modifications, to the version with no idle time. Again, the new procedures provided better results than the existing heuristics. Therefore, the procedures developed in this paper are the new heuristics of choice for both versions of the considered problem. [Received 09 October 2008; Revised 02 February 2009; Accepted 20 February 2009]

Abstract
This paper considers the single machine scheduling problem with linear earliness and quadratic tardiness costs, 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 these rules, Linear early/quadratic tardy dispatching rules are also considered, as well as a greedy-type procedure. Extensive experiments are performed to determine appropriate values for the parameters required by some of the heuristics. The computational tests show that the best results are given by the linear early/quadratic tardy dispatching rule. This procedure is also quite efficient, and can quickly solve even very large instances. [Received 15 December 2006; Revised 20 July 2007; Accepted 24 July 2007]