Optimal Two Stages Specially Structured Flow Shop Scheduling: Minimize the Rental Cost with Independent Setup Time

One of the earliest results in flow shop scheduling theory is an algorithm given by Johnson’s [1] for scheduling jobs on two or three machines to minimize the total elapsed time whenever the processing times of jobs are random. The present paper is an attempt to develop a heuristic algorithm for two stages specially structured flow shop scheduling in which the processing times of the jobs are not completely random, but bear a well defined relationship to one another to minimize the utilization time of machines and hence their rental cost under a specified rental policy. Further the processing times and independent set up times, each are associated with probabilities. A computer programme followed by a numerical illustration is given to validate the proposed algorithm.