Concise review of relaxations and approximation algorithms for nonidentical parallel-machi

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

times

Li Kai;Yang Shanlin

【期刊名称】《系统工程与电子技术（英文版）》 【年(卷),期】2008(019)004

【摘要】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. 【总页数】8页(827-834)

【关键词】parallel machine;scheduling;review;total weighted completion time;relaxation;algorithm 【作者】Li Kai;Yang Shanlin

【作者单位】School of Management,Hefei Univ.of Technology,Hefei 230009,P.R.China;School of Management,Hefei Univ.of Technology,Hefei 230009,P.R.China 【正文语种】中文 【中图分类】TN1