(Publisher of Peer Reviewed Open Access Journals)

International Journal of Advanced Computer Research (IJACR)

ISSN (Print):2249-7277    ISSN (Online):2277-7970
Volume-8 Issue-37 July-2018
Full-Text PDF
DOI:10.19101/IJACR.2018.835001
Paper Title : A metaheuristic for solving flowshop problem
Author Name : Peter Bamidele Shola and Asaju Laaro Bolaji
Abstract :

Discrete optimization is a class of computational expensive problems that are of practical interest and consequently have attracted the attention of many researchers over the years. Yet no single method has been found that could solve all instances of the problem. The no free launch theorem that confirms that no such general method (that can solve all the instances) could be found, has limited research activities in developing method for a specific class of instances of the problem. In this paper an algorithm for solving discrete optimization is presented. The algorithm is obtained from a hybrid continuous optimization algorithm using a technique devised by Clerc for particle swarm optimization (PSO). In the method, the addition, subtraction and multiplication operators are redefined to support discrete domain. The effectiveness of the algorithm was investigated on the flowshop problem using the makespan as the performance measure and the Taillard benchmark problem instances as the dataset. The result of the investigation is presented in this paper and compared with those from some existing algorithms, including genetic algorithm (GA), ant colony optimization (ACO), simulated annealing (SA), firefly and cockroach algorithms. Based on the experimental results, the algorithm is proposed as a competitive or a viable alternative for solving flowshop problems and possibly discrete optimization problems in general.

Keywords : Flowshop, Combinatorial, Optimization, Metaheuristics.
Cite this article : Peter Bamidele Shola and Asaju Laaro Bolaji, " A metaheuristic for solving flowshop problem " , International Journal of Advanced Computer Research (IJACR), Volume-8, Issue-37, July-2018 ,pp.180-190.DOI:10.19101/IJACR.2018.835001
References :
[1]Shola PB, Asaju LB. An algorithm for continuous optimization problems using hybrid particle updating method. Indonesian Journal of Electrical Engineering and Computer Science. 2016; 3(1):164-73.
[Crossref] [Google Scholar]
[2]Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research. 1993; 64(2):278-85.
[Crossref] [Google Scholar]
[3]Bagchi TP, Gupta JN, Sriskandarajah C. A review of TSP based approaches for flowshop scheduling. European Journal of Operational Research. 2006; 169(3):816-54.
[Crossref] [Google Scholar]
[4]Garey MR, Johnson DS, Sethi R. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research. 1976; 1(2):117-29.
[Crossref] [Google Scholar]
[5]Ignall E, Schrage L. Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research. 1965; 13(3):400-12.
[Crossref] [Google Scholar]
[6]Lomnicki ZA. A branch-and-bound algorithm for the exact solution of the three-machine scheduling problem. Operations Research. 1965; 16(1):89-100.
[Crossref] [Google Scholar]
[7]McMahon GB, Burton PG. Flow-shop scheduling with the branch-and-bound method. Operations Research. 1967; 15(3):473-81.
[Crossref] [Google Scholar]
[8]Horowitz E, Sahni S. Fundamentals of computer algorithms. Computer Science Press; 1978, p.626.
[Google Scholar]
[9]Johnson SM. Optimal two‐and three‐stage production schedules with setup times included. Naval Research Logistics. 1954; 1(1):61-8.
[Crossref] [Google Scholar]
[10]Sen T, Dileepan P, Gupia JN. The two-machine flowshop scheduling problem with total tardiness. Computers & Operations Research. 1989; 16(4):333-40.
[Crossref] [Google Scholar]
[11]Wang B, Li T, Shi C, Wang H. Scheduling two-machine flowshop with limited waiting times to minimize makespan. Indonesian Journal of Electrical Engineering and Computer Science. 2014; 12(4):3131-9.
[Crossref] [Google Scholar]
[12]Campbell HG, Dudek RA, Smith ML. A heuristic algorithm for the n job, m machine sequencing problem. Management Science. 1970; 16(10): 630-7.
[Crossref] [Google Scholar]
[13]Palmer DS. Sequencing jobs through a multi-stage process in the minimum total time-a quick method of obtaining a near optimum. Journal of the Operational Research Society. 1965; 16(1):101-7.
[Crossref] [Google Scholar]
[14]Hundal TS, Rajgopal J. An extension of Palmer s heuristic for the flow shop scheduling problem. International Journal of Production Research. 1988; 26(6):1119-24.
[Crossref] [Google Scholar]
[15]Nawaz M, Enscore EE, Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega. 1983; 11(1):91-5.
[Crossref] [Google Scholar]
[16]Grabowski J, Wodecki M. A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers & Operations Research. 2004; 31(11):1891-909.
[Crossref] [Google Scholar]
[17]Ek?io?lu B, Ek?io?lu SD, Jain P. A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods. Computers & Industrial Engineering. 2008; 54(1):1-11.
[Crossref] [Google Scholar]
[18]Ishibuchi H, Misaki S, Tanaka H. Modified simulated annealing algorithms for the flow shop sequencing problem. European Journal of Operational Research. 1995; 81(2):388-98.
[Crossref] [Google Scholar]
[19]Parthasarathy S, Rajendran C. A simulated annealing heuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence-dependent setup times of jobs-a case study. Production Planning & Control. 1997; 8(5):475-83.
[Crossref] [Google Scholar]
[20]Chen CL, Vempati VS, Aljaber N. An application of genetic algorithms for flow shop problems. European Journal of Operational Research. 1995; 80(2):389-96.
[Crossref] [Google Scholar]
[21]Chaudhry IA, Khan AM. Minimizing makespan for a no-wait flowshop using genetic algorithm. Sadhana. 2012; 37(6):695-707.
[Crossref] [Google Scholar]
[22]Cickova Z, Stevo S. Flow shop scheduling using differential evolution. Management Information Systems. 2010; 5(2):8-13.
[Google Scholar]
[23]Yagmahan B, Yenisey MM. A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications. 2010; 37(2):1361-8.
[Crossref] [Google Scholar]
[24]Ying KC, Liao CJ. An ant colony system for permutation flow-shop sequencing. Computers & Operations Research. 2004; 31(5):791-801.
[Crossref] [Google Scholar]
[25]Tasgetiren MF, Liang YC, Sevkli M, Gencyilmaz G. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research. 2007; 177(3):1930-47.
[Crossref] [Google Scholar]
[26]Ponnambalam SG, Jawahar N, Chandrasekaran S. Discrete particle swarm optimization algorithm for flowshop scheduling. In Particle Swarm Optimization 2009.
[Google Scholar]
[27]Reza Hejazi S, Saghafian S. Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research. 2005; 43(14):2895-929.
[Crossref] [Google Scholar]
[28]Ruiz R, Maroto C. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research. 2005; 165(2):479-94.
[Crossref] [Google Scholar]
[29]Tyagi N, Varshney RG, Chandramouli AB. Six decades of flowshop scheduling research. International Journal of Scientific & Engineering Research. 2013; 4(9):854-64.
[Google Scholar]
[30]Clerc M. Discrete particle optimization illustrated by the traveling salesman problem.2000.
[Google Scholar]
[31]Clerc M. Discrete particle swarm optimization, illustrated by the traveling salesman problem. In new optimization techniques in engineering 2004 (pp. 219-39). Springer Berlin Heidelberg.
[Crossref] [Google Scholar]
[32]Ramanan TR, Iqbal M, Umarali K. A particle swarm optimization approach for permutation flow shop scheduling problem. International Journal for Simulation and Multidisciplinary Design Optimization. 2014; 5:1-6.
[Crossref] [Google Scholar]
[33]Gupta A, Chauhan S. A heuristic algorithm for scheduling in a flow shop environment to minimize makespan. International Journal of Industrial Engineering Computations. 2015; 6(2):173-84.
[Crossref] [Google Scholar]
[34]Kwiecien J, Filipowicz B. Comparison of firefly and cockroach algorithms in selected discrete and combinatorial problems. Bulletin of the Polish Academy of Sciences Technical Sciences. 2014; 62(4):797-804.
[Crossref] [Google Scholar]