MINIMIZING EXPECTED MAKESPAN IN A 2-MACHINE STOCHASTIC OPEN SHOP WITH POISSON ARRIVAL

Longest expected processing time (LEPT) policy is a machine loading rule where out of all the jobs waiting to be processed by a machine, with their processing times following given probability distributions, the one with the largest expected processing time is chosen first. Using a method based on Markov process and dynamic programming, we show that a LEPT policy will minimize the expected makespan for a two-machine stochastic open shop with Poisson arrival for jobs. Processing time of any job at any machine is exponential. We assume that all jobs are identical but the two machines are not.