CLC number: TP393, O223

On-line Access:

Received: 2004-02-10

Revision Accepted: 2004-07-03

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3373

LIN Ling, TAN Zhi-yi, HE Yong. Deterministic and randomized scheduling problems under the *l** _{p}* norm on two identical machines[J]. Journal of Zhejiang University Science A, 2005, 6(1): 20~26.

@article{title="Deterministic and randomized scheduling problems under the *l** _{p}* norm on two identical machines",

author="LIN Ling, TAN Zhi-yi, HE Yong",

journal="Journal of Zhejiang University Science A",

volume="6",

number="1",

pages="20~26",

year="2005",

publisher="Zhejiang University Press & Springer",

doi="10.1631/jzus.2005.A0020"

}

%0 Journal Article

%T Deterministic and randomized scheduling problems under the *l** _{p}* norm on two identical machines

%A LIN Ling

%A TAN Zhi-yi

%A HE Yong

%J Journal of Zhejiang University SCIENCE A

%V 6

%N 1

%P 20~26

%@ 1673-565X

%D 2005

%I Zhejiang University Press & Springer

%DOI 10.1631/jzus.2005.A0020

TY - JOUR

T1 - Deterministic and randomized scheduling problems under the *l** _{p}* norm on two identical machines

A1 - LIN Ling

A1 - TAN Zhi-yi

A1 - HE Yong

J0 - Journal of Zhejiang University Science A

VL - 6

IS - 1

SP - 20

EP - 26

%@ 1673-565X

Y1 - 2005

PB - Zhejiang University Press & Springer

ER -

DOI - 10.1631/jzus.2005.A0020

**Abstract: **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

**
**

. INTRODUCTION

A scheduling problem is called online if jobs come one by one and it is required to schedule jobs irrevocably onto machines as soon as they are given, without any knowledge about jobs that follow later on. If some partially additional information about jobs is available in advance, and we cannot rearrange any job which has been assigned to machines, then it is called semi-online. Different partial information results in different semi-online problem. In the semi-online version with non-increasing job sizes (Graham,

We measure the performance of an algorithm for online and semi-online problems by its competitive ratio. For any fixed

The prime motivation of this study is as follows: So far most researches have been done in various scheduling models for the makespan measure, i.e. the

For the classical parallel machine scheduling problem

For the semi-online problem with decreasing job size

A closely related problem is the off-line problem

. OPTIMAL SEMI-ONLINE DETERMINISTIC ALGORITHM

If

(i)

(ii)

To prove (i), we suppose there exists a job sequence

Let

i.e.

Next we prove (ii). Consider the sequence

Now we return to the proof of the lemma. Given a non-increasing sequence of jobs

(a) Let

(b) Let

(c) Finally, let

Thus

Define

[(

=2(2

Since

Define

Define

Table

l_{p} |
Online version |
Semi-online version |
|||

Deterministic upper bound | Randomized lower bound | Deterministic upper bound | Randomized lower bound | ||

1.5 2 3 5 10 20 100 ( | 1.0817 1.1441 1.2311 1.3248 1.4083 1.4532 1.4905 1.5000 | 1.0622 1.1069 1.1659 1.2258 1.2775 1.3049 1.3276 1.3333 | 1.0071 1.0142 1.0277 1.0519 1.0933 1.1276 1.1587 1.1667 | 1.0070 1.0137 1.0265 1.0485 1.0842 1.1122 1.1367 1.1429 |

. CONCLUSION

* 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

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou
310027, China

Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn

Copyright © 2000 - Journal of Zhejiang University-SCIENCE

Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn

Copyright © 2000 - Journal of Zhejiang University-SCIENCE

Open peer comments: Debate/Discuss/Question/Opinion

<1>