A HYBRID SIMULATED ANNEALING APPROACH FOR SINGLE-MACHINE SCHEDULING PROBLEMS WITH NONREGULAR PENALTY-FUNCTIONS

被引：33

作者：

MITTENTHAL, J ^{[1
]}

RAGHAVACHARI, M ^{[1
]}

RANA, AI ^{[1
]}

机构：

[1] RENSSELAER POLYTECH INST,DEPT DECIS SCI & ENGN SYST,TROY,NY 12180

来源：

COMPUTERS & OPERATIONS RESEARCH | 1993年 / 20卷 / 02期

关键词：

D O I：

10.1016/0305-0548(93)90066-R

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

An algorithm is presented for single machine scheduling problems which have V-shaped optimal schedules. The algorithm is a hybrid of a greedy approach, followed by a simulated annealing search of the V-shaped sequence solution space. A number of non-regular objective functions, both with and without a common due date, are considered. In all test problems, the algorithm gives better solutions than the heuristics previously presented in the literature.

引用

页码：103 / 111

页数：9

共 22 条

[1]

Ackley D. H, 1987, CONNECTIONIST MACHIN

[2] SIMULTANEOUS MINIMIZATION OF MEAN AND VARIATION OF FLOW TIME AND WAITING TIME IN SINGLE-MACHINE SYSTEMS [J].

BAGCHI, U .

OPERATIONS RESEARCH, 1989, 37 (01) :118-125

[3] MINIMIZING MEAN SQUARED DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE [J].

BAGCHI, U ;

SULLIVAN, RS ;

CHANG, YL .

MANAGEMENT SCIENCE, 1987, 33 (07) :894-906

[4]

Baker K., 1974, INTRO SEQUENCING SCH

[5] SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW [J].

BAKER, KR ;

SCUDDER, GD .

OPERATIONS RESEARCH, 1990, 38 (01) :22-36

[6] THERMODYNAMICAL APPROACH TO THE TRAVELING SALESMAN PROBLEM - AN EFFICIENT SIMULATION ALGORITHM [J].

CERNY, V .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1985, 45 (01) :41-51

[7]

DE P, 1989, 8920 U DAYT SCH BUS

[8] MINIMIZING WAITING TIME VARIANCE IN SINGLE MACHINE PROBLEM [J].

EILON, S ;

CHOWDHURY, IG .

MANAGEMENT SCIENCE, 1977, 23 (06) :567-575

[9]

French S., 1982, SEQUENCING SCHEDULIN

[10]

GUPTA MC, 1990, J OPER RES SOC, V41, P767

← 1 2 3 →