Scheduling start time dependent jobs to minimize the total weighted completion time

被引：60

作者：

Bachman, A

Cheng, TCE

Janiak, A

Ng, CT

机构：

[1] Wroclaw Tech Univ, Inst Engn Cybernet, PL-50372 Wroclaw, Poland

[2] Hong Kong Polytech Univ, Hong Kong, Hong Kong, Peoples R China

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 2002年 / 53卷 / 06期

关键词：

computational analysis; scheduling; heuristics; start time dependent processing time; single machine;

D O I：

10.1057/palgrave.jors.2601359

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper deals with a single machine scheduling problem, with start time dependent job processing times, The job processing times are characterized by decreasing linear functions dependent on their start time.,,. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard, Some properties of special cases of the general problem are also given. Based on thew results. two heuristic algorithms are constructed and their performance is compared.

引用

页码：688 / 693

页数：6

共 15 条

[1] Scheduling with time dependent processing times: Review and extensions [J].