A hybrid imperialist competitive algorithm for single-machine scheduling problem with linear earliness and quadratic tardiness penalties

被引：13

作者：

Banisadr, A. H. ^{[1
]}

Zandieh, M. ^{[2
]}

Mahdavi, Iraj ^{[1
]}

机构：

[1] Mazandaran Univ Sci & Technol, Dept Ind Engn, Babol Sar, Iran

[2] Shahid Beheshti Univ, Dept Ind Management, Management & Accounting Fac, GC, Tehran, Iran

来源：

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY | 2013年 / 65卷 / 5-8期

关键词：

Hybridization; Imperialist competitive algorithm; Single-machine scheduling; Genetic algorithm; BEAM SEARCH HEURISTICS; COMPLETION TIMES; DEVIATION; COMMON;

D O I：

10.1007/s00170-012-4233-x

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we study single-machine scheduling problem when each job is considered with linear earliness and quadratic tardiness penalties with no machine idle time. Here the objective is to find the best sequence of jobs in the reasonable time. This model was studied in several researches, and some algorithms were proposed to solve it such as genetic algorithm. As the size of problem increased, such algorithms were not effective and efficient. Hence, we proposed the hybrid imperialist competitive algorithm. The proposed algorithm is based upon the imperialist competitive algorithm and genetic algorithm concepts. This algorithm was tested in problems with different sizes. The results denoted that the hybrid algorithm can solve different size of problem in reasonable time. This procedure showed its efficiency in medium- and large-sized problems as compared with other available methods.

引用

页码：981 / 989

页数：9

共 26 条

[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]

Atashpaz-Gargari E, 2007, IEEE C EVOL COMPUTAT, P4661, DOI 10.1109/cec.2007.4425083

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

BAGCHI, U ;

SULLIVAN, RS ;

CHANG, YL .

NAVAL RESEARCH LOGISTICS, 1986, 33 (02) :227-240

[4]

Baker K. R., 1974, Introduction to Sequencing and Scheduling"

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

BAKER, KR ;

SCUDDER, GD .

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

[6] MINIMIZING TOTAL TARDINESS ON ONE MACHINE IS NP-HARD [J].

DU, JZ ;

LEUNG, JYT .

MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) :483-495

[7] Colonial competitive algorithm A novel approach for PID controller design in MIMO distillation column process [J].

Gargari, Esmaeil Atashpaz ;

Hashemzadeh, Farzad ;

Rajabioun, Ramin ;

Lucas, Caro .

INTERNATIONAL JOURNAL OF INTELLIGENT COMPUTING AND CYBERNETICS, 2008, 1 (03) :337-355

[8]

Golberg D. E., 1989, GENETIC ALGORITHMS S, V1989, P36

[9] SINGLE-PROCESSOR AND MULTIPLE-PROCESSOR MODELS FOR MINIMIZING COMPLETION-TIME VARIANCE [J].

HALL, NG .

NAVAL RESEARCH LOGISTICS, 1986, 33 (01) :49-54

[10]

Holland J.H., 1992, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence

← 1 2 3 →