Article ID: | iaor19921725 |
Country: | United States |
Volume: | 40 |
Issue: | 1 |
Start Page Number: | 168 |
End Page Number: | 177 |
Publication Date: | Jan 1992 |
Journal: | Operations Research |
Authors: | Glazebrook K.D., Fay N.A. |
Keywords: | heuristics |
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.