Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F).

Li Kai; Yang Shanlin

doi:10.1016/S1004-4132(08)60160-7

Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F).

Li Kai
, Yang Shanlin

Hefei University of Technology

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	827-834
Number of pages	8
Journal	Journal of Systems Engineering and Electronics
Volume	19
Issue number	4
DOIs	https://doi.org/10.1016/S1004-4132(08)60160-7
State	Published - Aug 2008
Externally published	Yes

Keywords

algorithm
parallel machine
relaxation
review
scheduling
total weighted completion time

Access to Document

10.1016/S1004-4132(08)60160-7

Fingerprint

Dive into the research topics of 'Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F).'. Together they form a unique fingerprint.

Cite this

Kai, L., & Shanlin, Y. (2008). Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F). Journal of Systems Engineering and Electronics, 19(4), 827-834. https://doi.org/10.1016/S1004-4132(08)60160-7

Kai, Li ; Shanlin, Yang. / Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F). In: Journal of Systems Engineering and Electronics. 2008 ; Vol. 19, No. 4. pp. 827-834.

@article{169ab1d67c3a4d2b954d7512507bb29b,

title = "Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F).",

abstract = "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.",

keywords = "algorithm, parallel machine, relaxation, review, scheduling, total weighted completion time",

author = "Li Kai and Yang Shanlin",

year = "2008",

month = aug,

doi = "10.1016/S1004-4132(08)60160-7",

language = "英语",

volume = "19",

pages = "827--834",

journal = "Journal of Systems Engineering and Electronics",

issn = "1004-4132",

publisher = "Beijing Institute of Aerospace Information",

number = "4",

}

Kai, L & Shanlin, Y 2008, 'Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F).', Journal of Systems Engineering and Electronics, vol. 19, no. 4, pp. 827-834. https://doi.org/10.1016/S1004-4132(08)60160-7

Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F). / Kai, Li; Shanlin, Yang.
In: Journal of Systems Engineering and Electronics, Vol. 19, No. 4, 08.2008, p. 827-834.

Research output: Contribution to journal › Article › peer-review

TY - JOUR

T1 - Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F).

AU - Kai, Li

AU - Shanlin, Yang

PY - 2008/8

Y1 - 2008/8

N2 - 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.

AB - 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.

KW - algorithm

KW - parallel machine

KW - relaxation

KW - review

KW - scheduling

KW - total weighted completion time

UR - https://www.scopus.com/pages/publications/58649086760

U2 - 10.1016/S1004-4132(08)60160-7

DO - 10.1016/S1004-4132(08)60160-7

M3 - 文章

AN - SCOPUS:58649086760

SN - 1004-4132

VL - 19

SP - 827

EP - 834

JO - Journal of Systems Engineering and Electronics

JF - Journal of Systems Engineering and Electronics

IS - 4

ER -

Kai L, Shanlin Y. Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F). Journal of Systems Engineering and Electronics. 2008 Aug;19(4):827-834. doi: 10.1016/S1004-4132(08)60160-7

Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times This project was supported by the National Natural Science Foundation of China (70631003) and the Hefei University of Technology Foundation (071102F).

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this