Particle Swarm Optimization Algorithm For Single Machine Total

Particle Swarm Optimization Algorithm for Single Machine Total Weighted Tardiness Problem M. Fatih Tasgetiren Mehmet Sevkli Dept. of Management, Fatih University Dept. of Industrial Engineering, Fatih University 34500 Buyukcekmece, Istanbul, Turkey 34500 Buyukcekmece, Istanbul, Turkey Email: ftasgetiren@fatih.edu.tr Email: msevkli@fatih.edu.tr Yun-Chia Liang Gunes Gencyilmaz Dept. of Industrial Engineering and Management Dept. of Management, Yuan Ze University Istanbul Kultur University No 135 Yuan-Tung Road, Chung-Li, E5 Karayolu Uzeri, Sirinevler, Istanbul, Turkey Taoyuan County, Taiwan 320, R.O.C. Email: g.gencyilmaz@iku.edu.tr Email: ycliang@saturn.yzu.edu.tw Abstract: In

this paper we present a particle swarm towards the best particle in its restricted optimization algorithm to solve the single machine total weighted tardiness problem. A heuristic rule, the Smallest neighborhood [1]. Position Value (SPV) rule, is developed to enable the Since PSO was first introduced by Kennedy and continuous particle swarm optimization algorithm to be Eberhart [2, 3], it has been successfully applied to applied to all classes of sequencing problems, which are NP- optimize various continuous nonlinear functions. hard in the literature. A simple but very efficient local search method is embedded in the particle swarm optimization Although the applications of PSO on combinatorial algorithm. The computational results show that the particle optimization problems are still limited, PSO has swarm algorithm is able to find the optimal and best-known certain advantages such as easy to implement and solutions on all instances of widely used benchmarks from the computationally efficient. Therefore, this paper is OR libary. the first to employ PSO on solving single machine total weighted tardiness (SMTWT) problem which is I. INTRODUCTION a typical combinatorial optimization problem. Particle Swarm Optimization (PSO) is one of the McNaughton [4] first presented a scheduling latest population-based optimization methods, which problem that the objective is to minimize total does not use the filtering operation (such as penalty cost. He proved that an optimal solution crossover and/or mutation) and the members of the exists in which no job is split, so that only entire population are maintained through the search permutation schedules of the n jobs need to be procedure. In a PSO algorithm, each member is considered. Therefore, the SMTWT problem can be called “particle”, and each particle flies around in the stated as follows. Each of n jobs ( j = 1,..., n ) is to multi-dimensional search space with a velocity, be processed without preemption on a single which is constantly updated by the particle’s own machine that can handle no more than one job at a experience and the experience of the particle’s time. The processing and set-up requirements of any neighbors or the experience of the whole swarm. job are independent of its position in the sequence. Two variants of the PSO algorithm are developed, The release time of all jobs is zero. Thus, job j namely PSO with a local neighborhood, and PSO ( j = 1,..., n ) becomes available for processing at with a...

Website: www.fatih.edu.tr | Filesize: -
No of Page(s): 8
Download Particle Swarm Optimization Algorithm For Single Machine Total ....pdf