SEMI-ONLINE MULTIPROCESSOR SCHEDULING WITH BOUNDED JOBS
预知工件大小上界的平行机排序问题

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 boundedjobs are considered. The model only known the upper bound of each job inadvance 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 $C_{\rm max}$(minimize makespan) and $C_{\rm min}$(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 m. Finally, optimal algorithms are given for some situations.