A Hybrid Differential Evolution Algorithm for Job Shop Scheduling Problem to Minimize the Total Weighted Tardiness

This paper considers the job-shop problem with release dates and due dates, with the objective of minimizing the total weighted tardiness. A hybrid DE (HDE) is presented by combining differential evolution algorithm with the improved critical path algorithm on a disjunctive graph model. Firstly, a job-grouping-order (JPO) rule is presented to convert the continuous values of individuals (real vectors) in DE to job permutations. Secondly, after the global exploration based on DE, the improved critical path algorithm are used in a local search in order to improve the local search ability. An extensive computational experiment carried out on instances of the literature shows the performance of the proposed HDE algorithm.