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 2m/c cases and the makespan criterion, which proves the capability of both of them.

Keywords

flow shop lot streaming scheduling tabu search algorithm simulated annealing algorithm

References

Baker

K. R.

Introduction to sequencing and scheduling, 1974 (John Wiley & Sons Inc., New York).

Pinedo

Chao

Operations scheduling, 1997 (Irwin/McGraw-Hill, New York).

Sule

D. R.

Industrial scheduling, 1997 (PWS Publishing Company, Boston, Massachusetts).

Truscott

Production scheduling with capacity constrained transportation activities. J. Opl Managmt, 1986, 6, 333–348.

Potts

C. N.

Van Wassenhove

L. N.

Integrating scheduling with batching and lot sizing: A review of algorithm and complexity. J. Opl Res. Soc., 1992, 43(5), 395–406.

Potts

C. N.

Baker

K. R.

Flow shop scheduling with lot streaming. Ops Res. Lett., 1989, 8, 297–303.

Baker

K. R.

Lot streaming in the two-machine flow shop with set-up times. Ann. Ops Res., 1995, 57, 1–11.

Glass

C. A.

Gupta

J. N. D.

Potts

C. N.

Lot streaming in three-stage process. Eur. J. Opl Res., 1994, 75, 378–394.

Vickson

R. G.

Optimal lot streaming for multiple products in a two-machine flow shop. Eur. J. Opl Res., 1995, 85, 556–575.

10.

Sriskandarajah

Wagneur

Lot streaming and scheduling multiple products in two-machine no-wait flow shop. IIE Trans., 1999, 31, 695–707.

11.

Kumar

Bagchi

T. P.

Sriskandarajah

Lot streaming and scheduling heuristics for m-machine no-wait flow shop. Comput. and Ind. Engng, 2000, 38, 149–172.

12.

Hall

N. G.

Laporte

Selvarajah

Sriskandarajah

Scheduling and lot streaming in flow shops with no-wait in process. J. Scheduling, 2003, 6(4), 339–354.

13.

Liu

S. C.

A heuristic method for discrete lot streaming with variable sublots in a flow shop. Int. J. Advd Mfg Technol., 2003, 22, 662–668.

14.

Laarhovan

P. J. M.

Aarts

E. H. L.

Simulated annealing: Theory and applications, 1987 (Kluwer Academic, Dordrecht, The Netherlands).

15.

Ogbu

F. A.

Smith

D. K.

The application of the simulated annealing algorithm to the solution of the n/m/C_max flow shop problem. Comput. and Ops Res., 1990, 17, 243–253.

16.

Parthasarathy

Rajendran

An experimental evaluation of heuristics for scheduling in a real life flow shop with sequence-dependent setup time of jobs. Int. J. Prod. Econ, 1997, 49, 255–263.

17.

Glover

Kelly

J. P.

Laguna

Genetic algorithms and Tabu search: Hybrids for optimization. Comput. and Ops Res., 1995, 22(1), 111–134.

18.

Liu

Ong

H. L.

A comparative study of algorithms for the flow shop scheduling problem. Asia-Pacific J. Opl Res., 2002, 19, 205–222.