An Adaptive Genetic Algorithm to the Single Machine Scheduling Problem with Earliness and Tardiness Penalties

摘要

This paper deals with the Single Machine Scheduling Problem with Earliness and Tardiness Penalties, considering distinct due windows and sequence-dependent setup time. Due to its complexity, an adaptive genetic algorithm is proposed for solving it. Many search operators are used to explore the solution space where the choice probability for each operator depends on the success in a previous search. The initial population is generated by the combination between construct methods based on greedy, random and GRASP techniques. For each job sequence generated, a polynomial time algorithm is used for determining the processing initial optimal date to each job. During the evaluation process, the best individuals produced are added to a special group, called elite group. The individuals of this group are submitted to refinement, aiming to improve their quality. Three variations of this algorithm are submitted to computational test. The results show the effectiveness of the proposed algorithm.