Deterministic and randomized scheduling problems under the lp norm on two identical machines  

作　　者：林凌 谈之奕 何勇 

机构地区：[1]Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, China

出　　处：《Journal of Zhejiang University-Science A(Applied Physics & Engineering)》2005年第1期20-26,共7页浙江大学学报（英文版）A辑（应用物理与工程）

基　　金：Project supported by the National Natural Science Foundation of China (Nos. 10271110; 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE; China Project supported by the National Natural Science Foundation of China (Nos. 10271110; 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE; China

摘　　要：Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.

关 键 词：SEMI-ONLINE SCHEDULING RANDOMIZATION Competitive ratio 

分 类 号：TB114[理学—概率论与数理统计]