Iterative local search algorithm for no-wait flowshop scheduling problems to minimize makespan

Author

Wang, Chuyang ; Li, Xiaoping ; Wang, Qian

Author_Institution

Sch. of Comput. Sci. &Eng., Southeast Univ., Nanjing

fYear

2008

Firstpage

908

Lastpage

912

Abstract

In this paper, NP-hard no-wait flowshop scheduling problems with makespan minimization are considered. An iterative local search method is proposed which performs a randomized walk in the space of local optima until some stop criterion is satisfied. A perturbation mechanism and a compound neighborhood operator (or move ) are presented. The proposal is compared with the best algorithm so far. Experimental results show the proposed algorithm outperforms the existing one in effectiveness and in efficiency.

Keywords

computational complexity; dynamic programming; flow shop scheduling; iterative methods; minimisation; search problems; NP-hard problems; dynamic programming; iterative local search algorithm; makespan minimization; no-wait flowshop scheduling problems; perturbation mechanism; Chemical industry; Computer networks; Computer science; Computer science education; Dynamic programming; Iterative algorithms; Laboratories; Large-scale systems; Processor scheduling; Scheduling algorithm; Dynamic Programming; Local Search; Makespan; No-wait flowshop;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Supported Cooperative Work in Design, 2008. CSCWD 2008. 12th International Conference on

Conference_Location

Xi´an

Print_ISBN

978-1-4244-1650-9

Electronic_ISBN

978-1-4244-1651-6

Type

conf

DOI

10.1109/CSCWD.2008.4537100

Filename

4537100