A composite heuristic for the single machine early/tardy job scheduling problem

被引：18

作者：

Almeida, MT ^{[1
]}

Centeno, M ^{[1
]}

机构：

[1] Univ Tecn Lisboa, Inst Super Econ & Gestao, P-1200 Lisbon, Portugal

来源：

COMPUTERS & OPERATIONS RESEARCH | 1998年 / 25卷 / 7-8期

关键词：

job scheduling; tabu search; simulated annealing;

D O I：

10.1016/S0305-0548(97)00097-X

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The single machine early/tardy job scheduling problem (SMETP) is a NP-hard problem for which most properties of optimal solutions for single machine problems with regular objective function do not hold. In this paper we present a new composite heuristic for the SMETP that combines tabu search, simulated annealing and steepest descent techniques to generate near optimal schedules. Computational experience is reported for a set of randomly generated test problems. (C) 1998 Elsevier Science Ltd. All rights reserved.

引用

页码：625 / 635

页数：11

共 31 条

[1] DYNAMIC-PROGRAMMING STATE-SPACE RELAXATION FOR SINGLE-MACHINE SCHEDULING [J].

ABDULRAZAQ, TS ;

POTTS, CN .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1988, 39 (02) :141-152

[2] An SA/TS mixture algorithm for the scheduling tardiness problem [J].

Adenso-Diaz, B .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 88 (03) :516-524

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

BAKER, KR ;

SCUDDER, GD .

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

[4]

CENTENO M, 1993, THESIS U TECNICA LIS

[5]

CENTENO M, 1994, 294 CEMAPRE U TECHN

[6] A SINGLE-MACHINE MODEL FOR DETERMINATION OF OPTIMAL DUE DATES AND SEQUENCE [J].

CHAND, S ;

CHHAJED, D .

OPERATIONS RESEARCH, 1992, 40 (03) :596-602

[7]

DAVIS JS, 1988, SINGLE MACHINE SCHED

[8]

French S., 1990, SEQUENCING SCHEDULIN

[9] ONE-PROCESSOR SCHEDULING WITH SYMMETRIC EARLINESS AND TARDINESS PENALTIES [J].

GAREY, MR ;

TARJAN, RE ;

WILFONG, GT .

MATHEMATICS OF OPERATIONS RESEARCH, 1988, 13 (02) :330-348

[10]

Glover F., 1989, ORSA Journal on Computing, V1, P190, DOI [10.1287/ijoc.2.1.4, 10.1287/ijoc.1.3.190]

← 1 2 3 4 →