摘要
For most scheduling problems the set of machines is fixed initially and remainsunchanged for the duration of the problem. Recently Imreh and Nogaproposed to add theconcept of machine cost to scheduling problems and considered the so-called List Model problem.An online algorithm with a competitive ratio 1.618 was given while the lower bound is 4/3. Inthis paper, two different semi-online versions of this problem are studied. In the first case, it isassumed that the processing time of the largest job is known a priori. A semi-online algorithmis presented with the competitive ratio at most 1.5309 while the lower bound is 4/3. In thesecond case, it is assumed that the total processing time of all jobs is known in advance. Asemi-online algorithm is presented with the competitive ratio at most 1.414 while the lowerbound is 1.161. It is shown that the additional partial available information about the jobsleads to the possibility of constructing a schedule with a smaller competitive ratio than that ofonline algorithms.
基金
国家重点基础研究发展计划(973计划)，国家自然科学基金
