Tabu search and genetic algorithm for scheduling with total flow time minimization

Abstract

In this paper we confront the job shop scheduling problem with total flow time minimization. We start extending the disjunctive graph model used for makespan minimization to represent the version of the problem with total flow time minimization. Using this representation, we adapt local search neighborhood structures originally defined for makespan minimization. The proposed neighborhood structures are used in a genetic algorithm hybridized with a simple tabu search method, outperforming state-of-the-art methods in solving problem instances from several datasets