Stochastic two-machine flowshop scheduling problem with total completion time criterion

Most of the available literature on the stochastic two-machine flowshop scheduling problem, in which job processing times are assumed to be non-negative random variables, utilize the makespan criterion. A couple of researchers address the problem with total completion time criterion but with the assumption that processing times are independently and identically distributed. In this paper, we study a stochastic two-machine flowshop problem where processing times have distinct distributions and determine a schedule that minimizes the expected total completion times of all jobs (an NP-hard problem). We fully explore and present solution approaches for three different scenarios of the problem where processing times have independent normal distributions. The first scenario can be solved either exactly or approximately by some appropriate modifications of the respective existing exact Or heuristic solution approaches for the deterministic case of the problem. For the other two scenarios with normal processing times, we propose some exact efficient solution methods. Another scenario of the problem is also analyzed where processing times have general distributions. This scenario can be solved approximately by the classical methods for the deterministic problem which minimizes a lower bound on the optimal expected total completion time. Furthermore, we provide some numerical examples to illustrate the proposed scenarios. Significance: The vast majority of scheduling literature on the two-machine flowshop scheduling problem assumes that job processing times are known with certainty, However, in most real world flowshop systems, it is not appropriate to model processing times as deterministic. Moreover, the existing literature on flowshop scheduling with random processing times mainly uses the makespan criterion. In this paper, we address the two-machine flowshop scheduling problem to minimize the expected total completion time where job processing times have distinct distributions.