Tabu Search and Simulated Annealing Algorithms for Scheduling in Flow Shops with Lot Streaming

Abstract

This paper addresses the problem of making sequencing and scheduling decisions for n Jobs in m-machine flow shops with a lot sizing constraint. Lot streaming (lot sizing) is the process of creating sublots to move the completed portion of a production sublot to downstream machines. The planning decisions become more complex when lot streaming is allowed. There is scope for efficient metaheuristics for scheduling problems in an m machine flow shop with lot streaming. In recent years, much attention has been given to heuristics and search techniques. This paper proposes two metaheuristics, namely a simulated annealing algorithm (SA) and a tabu search algorithm (TABU), to evolve the optimal sequence for makespan and total flow time criteria in an m-machine flow shop with lot streaming. The algorithms are evaluated by means of comparison with Baker's algorithm for 2 m/c cases and the makespan criterion, which proves the capability of both of them.