Semi-online Multiprocessor Scheduling with Nonsimultaneous Machine Available Times

摘要：

This paper investigates scheduling problems on m parallel identical machines with nonsimultaneous machine available times. Each machine Ml is not available until time γi Jobs arrive one by one, and we are required to schedule jobs irrevocably on machines as soon as they are given, without any knowledge of the successive jobs. We study semi-online version of the problem while we known the largest processing time of all jobs in advance, the objective is to minimize the makespan, i.e. the maximum completion time of the processors. A lower bound (√33+3)/6 is showed when the number of machines is greater than 6, and a semi-online algorithm is presented with competitive ratio of at most 2 -1 / (m -1) ?

关键词： scheduling semi-online algorithm competitive ratio

作者: Haina SUN Yikun Huang

作者单位: Department of Fundamental Education Ningbo Institute of Technology, Zhejiang University Ningbo, P.R. The school of sciencesLinyi Normal UniversityLinyi, P.R.China, 276005

会议类型: 国际会议

会议名称: Third International Conference on Information and Computing(第三届信息与计算科学国际会议 ICIC 2010)

会议地点: 无锡

会议语种:英文

页码: 115-118

在线出版日期: 2010-06-04（万方平台首次上网日期，不代表论文的发表时间）