Scheduling on Uniform Nonsimultaneous Parallel Machines

被引：0

作者：

Grigoriu, Liliana ^{[1
]}

Friesen, Donald K. ^{[1
]}

机构：

[1] Univ Siegen, Fak Wirtschaftswissensch Wirtschaftsinformat & Wi, Kohlbettstr 15, D-57068 Siegen, Germany

来源：

OPERATIONS RESEARCH PROCEEDINGS 2016 | 2018年

关键词：

MULTIFIT;

D O I：

10.1007/978-3-319-55702-1_62

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of scheduling on uniform processors which may not start processing at the same time with the purpose of minimizing the maximum completion time. We provide a variant of the MULTIFIT algorithm which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and withinv root 6/2 times the optimal maximum completion time for problem instances with two processors. Experimental results suggest that our algorithm is a viable option for addressing this problem in practice.

引用

页码：467 / 473

页数：7