List scheduling revisited

被引：37

作者：

Schutten, JMJ

机构：

[1] Faculty of Mechanical Engineering, University of Twente, 7500 AE Enschede

来源：

OPERATIONS RESEARCH LETTERS | 1996年 / 18卷 / 04期

关键词：

scheduling; list scheduling; parallel machines; setup times; regular cost functions;

D O I：

10.1016/0167-6377(95)00057-7

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of scheduling n jobs on nz identical parallel machines to minimize a regular cost function. The standard list scheduling algorithm converts a list into a feasible schedule by focusing on the job start times. We prove that list schedules are dominant for this type of problem. Furthermore, we prove that an alternative list scheduling algorithm, focusing on the completion times rather than the start times, yields also dominant list schedules for problems with sequence dependent setup times.

引用

页码：167 / 170

页数：4

共 8 条

[1]

Baker KR., 1974, Introduction to Sequencing and Scheduling

[2] BOUNDS FOR LIST SCHEDULES ON UNIFORM PROCESSORS [J].