Tardiness minimization on parallel machines

被引：81

作者：

Azizoglu, M ^{[1
]}

Kirca, O ^{[1
]}

机构：

[1] Middle E Tech Univ, IE Dept, TR-06531 Ankara, Turkey

来源：

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS | 1998年 / 55卷 / 02期

关键词：

scheduling; parallel machines; total tardiness; branch and bound;

D O I：

10.1016/S0925-5273(98)00034-6

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total tardiness. We present properties that characterize the structure of an optimal schedule. We propose a branch and bound algorithm that incorporates the properties along with an efficient lower bounding scheme.We find that optimal solutions can be obtained in reasonable times for problems with up to 15 jobs. In the last part of the study we extend the results to uniform parallel machines. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：163 / 168

页数：6

共 12 条

[1] WEIGHTED-TARDINESS SCHEDULING ON PARALLEL MACHINES WITH PROPORTIONAL WEIGHTS [J].