Solving a multi-objective open shop scheduling problem by a novel hybrid ant colony optimization

被引：36

作者：

Panahi, Nadi ^{[1
]}

Tavakkoli-Moghaddam, Reza ^{[1
]}

机构：

[1] Univ Tehran, Dept Ind Engn, Coll Engn, POB 11155-4563, Tehran, Iran

来源：

EXPERT SYSTEMS WITH APPLICATIONS | 2011年 / 38卷 / 03期

关键词：

Scheduling; Open shop; Multi-objective optimization; Hybrid evolutionary algorithm; GENETIC ALGORITHM; SEARCH;

D O I：

10.1016/j.eswa.2010.08.073

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper considers an open shop scheduling problem that minimizes bi-objectives. namely makespan and total tardiness. This problem, due to its complexity, is ranked in the class of NP-hard problems. In this case, traditional approaches cannot reach to an optimal solution in a reasonable time. Thus, we propose an efficient method based on multi-objective simulated annealing and ant colony optimization, in order to solve the given problem. Furthermore a decoding operator is applied in order to improve the quality of generated schedules. Finally, we compare our computational results with a well-known multi-objective genetic algorithm, namely NSGA II. In addition, comparisons are made in single objective case. The outputs show encouraging results in the form of the solution quality. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：2817 / 2822

页数：6

共 20 条

[11] A hybrid genetic algorithm for the open shop scheduling problem [J].

Liaw, CF .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 124 (01) :28-42

[12] An efficient tabu search approach for the two-machine preemptive open shop scheduling problem [J].

Liaw, CF .

COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (14) :2081-2095

[13]

Liaw CF, 1999, IIE TRANS, V31, P457, DOI 10.1080/07408179908969848

[14]

Pinedo M., 1995, Scheduling: Theory, Algorithms, and Systems

[15] Competitive genetic algorithms for the open-shop scheduling problem [J].

Prins, C .

MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2000, 52 (03) :389-411

[16] Approximation algorithms for the multiprocessor open shop scheduling problem [J].

Schuurman, P ;

Woeginger, GJ .

OPERATIONS RESEARCH LETTERS, 1999, 24 (04) :157-163

[17]

Sha DY, 2006, P 36 INT C COMP IND, P702

[18]

SHAA DY, COMPUTERS OPERATIONS, V35, P3243

[19]

Sule DileepR., 1997, Industrial Scheduling

[20] BENCHMARKS FOR BASIC SCHEDULING PROBLEMS [J].

TAILLARD, E .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 64 (02) :278-285

← 1 2 →