SCHEDULING TWO GROUPS OF JOBS WITH INCOMPLETE INFORMATION

摘要

In real world situations, most scheduling problems occur neither as complete off-line nor ascomplete on-line models. Most likely, a problem arises as an on-line model with some partialinformation. In this article, we consider such a model. We study the scheduling problem P(n1,n2),where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon asall jobs in the first group are assigned, the second job group appears. The objective is to minimize thelongest 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 forthe general case. The main contribution of this paper is to discuss the impact of the quantity ofavailable information in designing an on-line algorithm. It is interesting to note that the absence ofeven a little bit information may significantly affect the performance of an algorithm.