On-line capacitated single machine scheduling and its heuristics

On-line capacitated single machine scheduling and its heuristics

0.00 Avg rating0 Votes
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:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.