EFFECTIVE HEURISTICS FOR THE SINGLE-MACHINE SEQUENCING PROBLEM WITH READY TIMES

被引：23

作者：

LIU, JY

MACCARTHY, BL

机构：

[1] Department of Manufacturing Engineering and Operations Management, University of Nottingham

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 1991年 / 29卷 / 08期

关键词：

D O I：

10.1080/00207549108948029

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

In this paper we consider the single machine sequencing problem with different ready times in which the objective is to minimize the mean completion time (or mean flow time, or the sum of completion times, or the sum of flow times). We propose some heuristics for the problem and give conditions under which the heuristics give optimal sequences. A MILP formulation and a branch and bound procedure are used to generate optimal solutions for comparison with those which the heuristics generate. Computational testing shows that the heuristics yeild excellent sequences in a very short time. Full computational details and results are given in this paper.

引用

页码：1521 / 1533

页数：13

共 9 条

[1]

Bianco L., Ricciardelli S., Scheduling of a single machine to minimize weighted completiontimesubjectto release data, Naval Research Logistics Quarterly, 29, pp. 151-167, (1982)

[2]

Deogun J.S., On scheduling with ready times to minimize mean flow time, Computer Journal, 26, pp. 320-328, (1983)

[3]

Dessouky M.I., Deogun J.S., Sequencing jobs with unequal ready timesto minimize mean flow time. SIAM, J. Computing, 10, pp. 192-202, (1981)

[4]

French S., Sequencing and Scheduling: An Introduction to the Mathematics Ofthe Job Shop, (1982)

[5]

Grabowski J., Block approach for single-machine scheduling with release dates and due dates, European Journal of Operations Research, 26, pp. 278-285, (1986)

[6]

Hariri A., Poits C.N., An algorithm for single machine sequencing with release dates to minimize total weighted completiontime, Discrete Applied Mathematics, 5, pp. 99-109, (1983)

[7]

Kise H., Baraki T., Mine H., Asolvablecase of one-machine schedulingproblem with ready and due times, Operations Research, 26, pp. 121-126, (1978)

[8]

Rinnooy Kan A., Machine Scheduling Problem: Classification, Complexity, and Computations, (1976)

[9]

Stafford E.F., On the development ofa mixed integerlinear programmingmodelfor the standard N-job, M-machine f1owshop sequencing problem, Journal of the Operational Research Society, 39, pp. 1163-1174, (1988)

← 1 →