Optimal preemptive online scheduling to minimize lp norm on two processors

Donglei Du; Xiaoyue Jiang; Guochuan Zhang

doi:10.3934/jimo.2005.1.345

Article Contents

2005, Volume 1, Issue 3: 345-351. Doi: 10.3934/jimo.2005.1.345

This issue Previous Article Algorithms by layer-decomposition for the subgraph recognition problem with attributes Next Article A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time

Optimal preemptive online scheduling to minimize lp norm on two processors

1.
Faculty of Business Administration, University of New Brunswick, P.O.Box 4400, Fredericton, NB E3B 5A3
2.
College of Engineering, Louisiana State University, Baton Rouge, LA 70803
3.
Department of Mathematics, Zhejiang University, Hangzhou 310027, PR

Received: July 31, 2004

Revised: December 31, 2004

Published: June 2005

Abstract Related Papers Cited by

Abstract

We consider an on-line scheduling problem, where jobs arrive one by one to be scheduled on two identical parallel processors with preemption. The objective is to minimize the machine completion time vector with respect to the $l_p$ norm. We present a best possible deterministic on-line scheduling algorithm along with a matching lower bound.

Keywords:

Mathematics Subject Classification: 90B35, 68Q17, 68Q25, 68W25, 68W40.

Citation:

Article Metrics

HTML views() PDF downloads(53) Cited by(0)

Optimal preemptive online scheduling to minimize lp norm on two processors

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

Optimal preemptive online scheduling to minimize lp norm on two processors

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content