On a “No Arrivals” Heuristic for Single Machine Stochastic Scheduling

In many contexts in which resource allocation takes place in a stochastic environment, new jobs arrive over time. Incorporation of an arrivals process into the scheduling model significantly complicates the problem of determining optimal strategies. Earlier computational studies suggest that for a large class of single machine problems often little is lost by adopting a heuristic that (essentially) ignores the arrivals process. Cases are described in which the heuristic yields an optimal strategy and analytical tools are developed that enable its evaluation. The heuristic performs well, both when arrivals are rare and when arrivals of good jobs are frequent.