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.

Keyword

Flowshop, Combinatorial, Optimization, Metaheuristics.

Cite this article

Refference

[1][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.

[2][2]Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research. 1993; 64(2):278-85.

[3][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.

[4][4]Garey MR, Johnson DS, Sethi R. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research. 1976; 1(2):117-29.

[5][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.

[6][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.

[7][7]McMahon GB, Burton PG. Flow-shop scheduling with the branch-and-bound method. Operations Research. 1967; 15(3):473-81.

[8][8]Horowitz E, Sahni S. Fundamentals of computer algorithms. Computer Science Press; 1978, p.626.

[9][9]Johnson SM. Optimal two‐and three‐stage production schedules with setup times included. Naval Research Logistics. 1954; 1(1):61-8.

[10][10]Sen T, Dileepan P, Gupia JN. The two-machine flowshop scheduling problem with total tardiness. Computers & Operations Research. 1989; 16(4):333-40.

[11][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.

[12][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.

[13][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.

[14][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.

[15][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.

[16][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.

[17][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.

[18][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.

[19][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.

[20][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.

[21][21]Chaudhry IA, Khan AM. Minimizing makespan for a no-wait flowshop using genetic algorithm. Sadhana. 2012; 37(6):695-707.

[22][22]Cickova Z, Stevo S. Flow shop scheduling using differential evolution. Management Information Systems. 2010; 5(2):8-13.

[23][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.

[24][24]Ying KC, Liao CJ. An ant colony system for permutation flow-shop sequencing. Computers & Operations Research. 2004; 31(5):791-801.

[25][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.

[26][26]Ponnambalam SG, Jawahar N, Chandrasekaran S. Discrete particle swarm optimization algorithm for flowshop scheduling. In Particle Swarm Optimization 2009.

[27][27]Reza Hejazi S, Saghafian S. Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research. 2005; 43(14):2895-929.

[28][28]Ruiz R, Maroto C. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research. 2005; 165(2):479-94.

[29][29]Tyagi N, Varshney RG, Chandramouli AB. Six decades of flowshop scheduling research. International Journal of Scientific & Engineering Research. 2013; 4(9):854-64.

[30][30]Clerc M. Discrete particle optimization illustrated by the traveling salesman problem.2000.

[31][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.

[32][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.

[33][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.

[34][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.