|
Deterministic and randomized scheduling problems under the lp norm on two identical machines
LIN Ling, TAN Zhi-yi, HE Yong
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2005, 6(1): 20-26.
https://doi.org/10.1631/jzus.2005.A0020
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.
|
|
Tools to make C programs safe: a deeper study
WANG Ji-min, PING Ling-di, PAN Xue-zeng, SHEN Hai-bin, YAN Xiao-lang
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2005, 6(1): 63-70.
https://doi.org/10.1631/jzus.2005.A0063
The C programming language is expressive and flexible, but not safe; as its expressive power and flexibility are obtained through unsafe language features, and improper use of these features can lead to program bugs whose causes are hard to identify. Since C is widely used, and it is impractical to rewrite all existing C programs in safe languages, so ways must be found to make C programs safe. This paper deals with the unsafe features of C and presents a survey on existing solutions to make C programs safe. We have studied binary-level instrumentation tools, source checkers, source-level instrumentation tools and safe dialects of C, and present a comparison of different solutions, summarized the strengths and weaknesses of different classes of solutions, and show measures that could possibly improve the accuracy or alleviate the overhead of existing solutions.
|
3 articles
|