在线约束单机排序问题的启发式算法

由于约束单机排序问题是经典装箱问题的一种推广并且同经典装箱问题有一些相同的特征。本文主要讨论了经典装箱问题的一些启发式算法在在线约束单机排序问题上的推广和最坏界估计。

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, we mainly study its on-line scheduling and apply 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.