Access Restriction

Author Zhang, Guochuan ♦ Cai, Xiaoqiang ♦ Wong, C. K.
Source SpringerLink
Content type Text
Publisher Systems Engineering Society of China
File Format PDF
Copyright Year ©2003
Language English
Subject Domain (in DDC) Technology ♦ Engineering & allied operations
Subject Keyword Machine scheduling ♦ worst-case analysis ♦ on-line algorithm ♦ Systems and Information Theory in Engineering ♦ Game Theory/Mathematical Methods ♦ Operations Research/Decision Theory
Abstract In real world situations, most scheduling problems occur neither as complete off-line nor as complete on-line models. Most likely, a problem arises as an on-line model with some partial information. In this article, we consider such a model. We study the scheduling problem P(n $_{1}$,n $_{2}$), where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon as all jobs in the first group are assigned, the second job group appears. The objective is to minimize the longest job completion time (makespan). We show a lower bound of 3/2 even for very special cases. Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed for the general case. The main contribution of this paper is to discuss the impact of the quantity of available information in designing an on-line algorithm. It is interesting to note that the absence of even a little bit information may significantly affect the performance of an algorithm.
ISSN 10043756
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2003-01-01
Publisher Place Beijing
e-ISSN 18619576
Journal Journal of Systems Science and Systems Engineering
Volume Number 12
Issue Number 1
Page Count 9
Starting Page 73
Ending Page 81

Open content in new tab

   Open content in new tab
Source: SpringerLink