A modified Variable Neighborhood Search for minimizing the makespan on identical parallel machines

Author

Sevkli, Mehmet ; Uysal, Hilmi

Author_Institution

Ind. Eng. Dept., Fatih Univ., Istanbul, Turkey

fYear

2009

fDate

6-9 July 2009

Firstpage

108

Lastpage

111

Abstract

Variable Neighborhood Search (VNS) is one of the most recent metaheuristics used for problem solving in which a systematic change of neighborhood within a local search is carried out. The idea is to build the best local search and shake operations based on neighbourhood structure available. In this paper, a modified version of VNS algorithm proposed for identical parallel machines scheduling problems with the objective function of minimizing makespan. The proposed VNS algorithm was tested 150 randomly generated problems with different jobs and machines. The results gained by modified VNS (MVNS) algorithm are presented and compared with the both Genetic Algorithm (GA) and Longest Processing Time (LPT) solutions. It is concluded that the MVNS algorithms outperform the both GA and LPT.

Keywords

genetic algorithms; parallel machines; scheduling; search problems; genetic algorithm; identical parallel machine; local search; longest processing time; objective function; parallel machine scheduling problem; variable neighborhood search; Genetic algorithms; Industrial engineering; Job shop scheduling; Optimal scheduling; Parallel machines; Polynomials; Problem-solving; Processor scheduling; Scheduling algorithm; Testing; Identical Parallel Machine Scheduling; Makespan; Variable neighboorhood search;

fLanguage

English

Publisher

ieee

Conference_Titel

Computers & Industrial Engineering, 2009. CIE 2009. International Conference on

Conference_Location

Troyes

Print_ISBN

978-1-4244-4135-8

Electronic_ISBN

978-1-4244-4136-5

Type

conf

DOI

10.1109/ICCIE.2009.5223485

Filename

5223485