Semi-Online Multiprocessor Scheduling with Bounded Jobs
WU Yong(1), YANG Qifan(2)
Author information+
(1)Department of Fundamental Education, Ningbo Institute of Technology, Zhejiang University, Ningbo 315100;(2)Department of Mathematics, Zhejiang University, Hangzhou 310027
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 (minimize makespan) and (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.
WU Yong
, YANG Qifan. , {{custom_author.name_en}}.
Semi-Online Multiprocessor Scheduling with Bounded Jobs. Journal of Systems Science and Mathematical Sciences, 2010, 30(4): 441-448 https://doi.org/10.12341/jssms08959