Article ID: | iaor2000806 |
Country: | China |
Volume: | 21 |
Issue: | 4 |
Start Page Number: | 618 |
End Page Number: | 626 |
Publication Date: | Nov 1998 |
Journal: | Acta Mathematicae Applicatae Sinica |
Authors: | Xing W. |
Capacitated single machine scheduling (CSMS) problem is a variant of the classical bin-packing problems. In this paper, the author mainly studies its on-line scheduling and applies some heuristics for bin-packing like next-fit (NF), next-fit-decreasing (NFD), next-fit-increasing (NFI), first-fit (FF) and first-fit-decreasing (FFD), to CSMS. There are four sections in this paper. Data constraints are given in Section 1. Section 2 and 3 respectively present the worst case ratios when NF, NFD, NFI, FF, FFD are applied. Finally conclusions are given in Section 4.