预知工件大小上界的平行机排序问题

SEMI-ONLINE MULTIPROCESSOR SCHEDULING WITH BOUNDED JOBS

平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡,大型计算中的并行计算,柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:C_(max)(极小化机器最大负载makespan)和C_(min)(极大化机器最小负载).在不同的目标下,针对m台平行机的一般情况均给出了问题的下界并设计了半在线算法,某些情况下设计的算法是最优算法.

Machine scheduling problems may occur in many applications such as load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc. In this paper, semi-online multiprocessor scheduling problems with bounded jobs are considered. The model only known the upper bound of each job in advance and the model known both the optimal value and the upper bound of each job in advance are analyzed. Motivated by issues of fair resource allocation and quality of service, two goals Cmax（minimize makespan） and Cmin（maximize the minimum machine load） for each model are studied. It is shown that the lower bound and design semi-online algorithm for each problem when the number of machine is rn. Finally, optimal algorithms are given for some situations.