### Scheduling two groups of jobs with incomplete informationScheduling two groups of jobs with incomplete information

Access Restriction
Subscribed

 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