On-line capacitated single machine scheduling and its heuristics

Capacitated single machine scheduling (CSMS) problem is a variant of the classical bin-packing problems. In this paper, the author mainly studies 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. Sections 2 and 3 respectively present the worst case ratios when NF, NFD, NFI, FF, FFD are applied. Finally conclusions are given in Section 4.