| Article ID: | iaor19881136 |
| Country: | Netherlands |
| Volume: | 31 |
| Issue: | 5 |
| Start Page Number: | 221 |
| End Page Number: | 225 |
| Publication Date: | Jun 1989 |
| Journal: | Information Processing Letters |
| Authors: | Ramanan Prakash |
| Keywords: | scheduling |
This paper, presents the Smart Next Fit algorithm for on-line bin packing, which is obtained by slightly modifying the Next Fit algorithm. For any list of items, this algorithm uses the smallest number of bins among all on-line algorithms that have only one active bin at any time. The paper analyses its average-case performance when the item sizes are uniformly distributed over [0,