AN LPT-BOUND FOR A PARALLEL MULTIPROCESSOR SCHEDULING PROBLEM

被引：1

作者：

HARCHE, F

SESHADRI, S

机构：

[1] Department of Statistics and Operations Research, Leonard N. Stern School of Business, York University, New York

来源：

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS | 1995年 / 196卷 / 01期

关键词：

D O I：

10.1006/jmaa.1995.1405

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper is concerned with the problem of assigning n jobs with known processing times to m machines to minimize makespan. Each machine has a fixed capacity expressed as the maximum number of jobs that can be assigned to it. We investigate the worst-case behavior of the longest processing time heuristic for this problem. For the case of two machines with equal capacity, it is shown that the worst case error bound is 7/6. (C) 1995 Academic Press, Inc.

引用

页码：181 / 195

页数：15

共 14 条

[1]

Ammons J.C., Lofcren C.B., McGinnis L.F., A large scale machine loading problem in flexible assembly, Ann. Oper. Res, 3, pp. 319-322, (1985)

[2]

Ball M.O., Magazine M.J., Sequencing of insertions in printed circuit board assembly, Oper. Res, 36, pp. 192-201, (1986)

[3]

Baxter L.A., Fiarche F., On the optimal assembly of series-parallel systems, Oper. Res. Lett, 11, pp. 153-157, (1992)

[4]

Baxter L.A., Harche F., Tovey C.A., A Simple Heuristic to Minimize Makespan on Parallel Processors with Unequal Capacities, (1993)

[5]

Coffman E.G., Lueker G.S., Rinnooy Kan A.H.G., Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics, Management Sci, 34, pp. 266-290, (1988)

[6]

Graham R.L., Bounds for certain multiprocessing anomalies, Bell System Technol. J, 45, pp. 563-581, (1966)

[7]

Graham R.L., Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math, 17, pp. 263-269, (1969)

[8]

Harche F., Analysis of a Capacitated Parallel Multi Processor Scheduling Problem, (1993)

[9]

Lofgren C.B., Machine configuration in flexible assembly systems, Proceedings of the Materials Handling Focus'85, (1985)

[10]

Lofgren C.B., Tovey C.A., Performance Bounds on Machine Configuration in Flexible Manufacturing Systems, (1985)

← 1 2 →