Flexible job-shop scheduling with transportation resources

Abstract

This paper addresses an extension of the flexible job-shop scheduling problem where transportation resources are explicitly considered when moving jobs from one machine to another. Operations should be assigned to and scheduled on machines and vehicles and the routes of vehicles should be determined. We extend the classical disjunctive graph model to include transportation operations and exploit the graph in an integrated approach to solve the problem. We propose a metaheuristic using a neighborhood function that allows a large set of moves to be explored. As the exact computation of the makespan of every move is time-consuming, we present a move evaluation procedure that runs in constant time (which does not depend on the size of the instance) to choose a promising move in the neighborhood of a solution. This move evaluation procedure is used in a tabu search framework. Computational results show the efficiency of the proposed approach, the quality of the move evaluation procedure and the relevance of explicitly modeling transportation resources. New benchmark instances are also proposed.