Flowshop scheduling problem to minimize total completion time with random and bounded processing times

Abstract

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.

Keywords:

• scheduling
• flowshop
• uncertainty
• geometrical approach
• total completion time

Acknowledgements

The research of the first author was partially supported by INTAS (project 00-217). The research of the second author was supported by Kuwait University Research Administration (project EM 01/01). The research of the third author was supported by NSC of Taiwan under projects NSC 89-2416-H002-039 and NSC 91-2416-H-002-006.