Two Parallel Machines Scheduling With A Potential Machine Release Time

This paper studies a two-parallel identical machines scheduling problem with a potential machine release time. There is a non-availabilty period randomly occurred at time zero. The non-availabilty period a equals either zero or a, where the probability ofα= a is q. We consider the objcetive of minimizing the expected total completion times of jobs, as well as the objective of minimizing the expected maximum completion time of jobs.In the paper, two types of algorithms, namely dynamical algorithms and static algorithms, are studied. For the problem P2|α|E[∑Cj] of minimizing the expected total completion times of jobs, optimal dynamical algorithm and optimal static algorithm are designed. For the problem P2|α|E[Cmax] of minimizing the expected maximum completion time of jobs, we first show the worst case ratio of dynamical LPT algorithm is 7/6; then, a new algorithm M-LPT is presented and proved to have a worst case ratio of...