Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times

被引：0

作者：

Li Kai Yang Shanlin School of ManagementHefei Univof TechnologyHefei PRChina ^{[230009
]}

机构：

来源：

JournalofSystemsEngineeringandElectronics | 2008年 / 04期

关键词：

parallel machine; scheduling; review; total weighted completion time; relaxation; algorithm;

D O I：

暂无

中图分类号：

TP338.6 [并行计算机];

学科分类号：

081201 ;

摘要：

A class of nonidentical parallel machine scheduling problems are considered in which the goal is to minimize the total weighted completion time.Models and relaxations are collected.Most of these problems are NP-hard,in the strong sense,or open problems,therefore approximation algorithms are studied.The review reveals that there exist some potential areas worthy of further research.

引用

页码：827 / 834

页数：8

共 17 条

[1] 平行机中关于关于同类机近似算法的研究 [J].

陈祥伟 .

应用数学学报, 2004, (04) :599-607

[2] 极小化加权完工时间和的调度问题 [J].

赵传立 ;

张庆灵 ;

唐恒永 ;

不详 .

东北大学学报 , 2003, (06) :515-518

[3]

Parallel machine scheduling with earliness–tardiness penalties and additional resource constraints[J] . José A. Ventura,Daecheol Kim.Computers and Operations Research . 2003 (13)

[4] Experimental comparison of approximation algorithms for scheduling unrelated parallel machines [J].

Vredeveld, T ;

Hurkens, C .

INFORMS JOURNAL ON COMPUTING, 2002, 14 (02) :175-189

[5]

Job shop scheduling with alternative process plans[J] . Christoph S. Thomalla.International Journal of Production Economics . 2001 (1)

[6] A 3/2-approximation algorithm for parallel machine scheduling with controllable processing times [J].

Zhang, F ;

Tang, GC ;

Chen, ZL .

OPERATIONS RESEARCH LETTERS, 2001, 29 (01) :41-47

[7] Convex quadratic and semidefinite programming relaxations in scheduling [J].

Skutella, M .

JOURNAL OF THE ACM, 2001, 48 (02) :206-242

[8] Minimizing average completion time in the presence of release dates [J].

Cynthia Phillips ;

Clifford Stein ;

Joel Wein .

Mathematical Programming, 1998, 82 :199-223

[9] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].

Goemans, MX ;

Williamson, DP .

JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145

[10] WEIGHTED FLOW TIME-BOUNDS FOR SCHEDULING IDENTICAL PROCESSORS [J].

WEBSTER, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 80 (01) :103-111

← 1 2 →