Extended GRASP for the job shop scheduling problem with total weighted tardiness objective

The paper proposes a heuristic for the job shop scheduling problem with minimizing the total weighted tardiness of jobs as objective. It is built upon the well known metaheuristic GRASP and strengthened with an inclusion of specific local search components. The design is based on an advanced disjunctive graph model which enables capturing solution schedules through a tree graph called critical tree. The tree graph allows for effectively steering a first-descent search algorithm which further incorporates powerful neighborhood operators and a fast move evaluation procedure based on heads updating. Additionally, amplifying and path relinking is adaptively applied to the best schedules discovered. We present computational results of the new heuristic on two famous sets of benchmark instances, we identify ten new best solutions, and we demonstrate the high potential of the approach through a comparison with state-of-the-art methods.