A Comparative Study on Performance of "ant colony system" and "Linear Programming" methods in the Modeling of the Flow Shop Scheduling

Subject Areas : Industrial Management

Said Esfandyari ¹ , Ali Morovati Sharif Abadi ² , Seyed Habibolah Mirghafouri ³ , Hamid Reza Kadkhodazadeh ⁴

1 - M.A in Management, Jahad Daneshgahi Higher Education Institute, Yazd Branch
2 - Assistant Professor, University of Yazd, Yazd, Iran
3 - Associate Professor, University of Yazd, Yazd, Iran
4 - M.A in Management, Jahad Daneshgahi Higher Education Institute, Yazd Branch

Received: 2018-01-08 Accepted : 2018-01-08 Published : 2013-05-22

Keywords:

Abstract :

Although linear programming is used widely in the world, its inefficiency in dealing with difficult problems is concerned. With the advancement in science and dealing with various problems, it tends to have problems in mass production in a short time. Heuristic and meta-heuristic techniques are the latest achievements of nonlinear programming for solving the similar problem. One area that requires programming applications in mass production is NP-scheduling problems. This paper aims at modeling and comparing the two methods of Linear Programming and Ant Colony System Algorithm in flexible flow shop scheduling problem according to the number of jobs and machines. This study is based on comparing the index of time processing, the number of constraints, optimality, and the memory size of the random numbers. Using Quasi-experimental research method, software testing tools are C-sharp and Lingo for the ant colony algorithm and linear programming respectively. The results show that linear programming model has higher performance when machines and jobs are in low numbers; however, with the rise of the machines and jobs, Ant Colony System algorithm has proven high efficiency.    

References:

1-   Artigues, C., & Gendreau M., & Rousseau, L.M., Vergnaud A. (2009). Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound. Computers & Operations Research, 36(8), 2330 – 2340.

2-   Balseiro, S.R., & Loiseau, I., & Ramonet J. (2011). An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows. Computers & Operations Research, 38(2), 954–966.

3-   Brucker, P. (2007). Scheduling Algorithms, 15(1), Heidelberg.

4-   Dannenbring, D. G. (1977). An evaluation of flowshop sequencing heuristics. Management Science, 23(11), 1174–1182.

5-   Dorigo, M., & Gambardella, L. M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transaction on Evolutionary Computation, 1(1), 53-63.

6-   Dorigo, M., & Di Caro, G. (1999). The ant colony optimization meta-heuristic. In D.Corne, M. Dorigo, & F. Glover (Eds.), New ideas in optimization .London, UK: McGraw-Hill, 11-32.

7-   Ebadi, A., Moslehi, G. (2011). Mathematical models for preemptive shop scheduling problems. Computers & Operations Research, 39(7), 1605-1614

8-   Gicquel, C. & Hege, L. & Minoux, M., & van Canneyt W. (2012). A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints. Computers & Operations Research, 39629–636.

9-   Gupta, J. N. D. (1971). An improved combinatorial algorithm for the flowshop scheduling problem. Operations Research, 19, 1753–1758.

10-    Huang, Y.M., & Lin J.C. (2010).  A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling problems. Expert Systems with Applications, 38(5), 5438-5447.

11-    Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68.

12-    Leung, C.W., & Wong T.N., & Mak K.L., & Fung R.Y.K. (2010). Integrated process planning and scheduling by an agent-based ant colony optimization. Computers & Industrial Engineering, 59(1), 166–180.

13-    Lin, H. T., & Lee, H. T., & Pan, W.J. (2008). Heuristics for scheduling in a no-wait open shop with movable dedicated machines. Int. J. Production Economics, 111, 368–377.

14-    Mehregan MR. (2002). Performance evaluation of organizations using quantitative data envelopment analysis. Tehran: Tehran University, 147-53.

15-    Mohamadi, A., & Jamalnia, A. (2007). Ant colony and its application in preventive maintainance. shahed university.

16-    Momeni, M. (2011). New topic in operation research. Tehran. Tehran University.

17-    Nasiri, F., & Ebrahimi, A. (2009). Evaluation of ant colony for solving defects and export overruns. Twenty- fourth international conferences on electricity. 

18-    Neto, T. & Filho, G. (2011). An Ant Colony Optimization approach to a permutational flow shop scheduling problem with outsourcing allowed. Computers & Operations Research, 38(9), 1-19.

19-    Onder Bozdogan, A., & Efe, M. (2011). Improved assignment with ant colony optimization for multi-target tracking. Expert Systems with Applications, 38(8), 9172-9178.

20-    Pinedo, M. (2005). Planning and Scheduling in Manufacturing and Services .Springer, 5(1), 10-17.

21-    Pinedo, M. (2009). Planning and Scheduling in Manufacturing and Services Second Edition. Springer, New York, Verlag.

22-    Santos, L., & Coutinho-Rodrigues, J. (2010) .Current J.R. An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportation Research Part, 44(4), 246–266.

23-    Schluter, M., & Egea, J.A., & Banga, J.R. (2009). Extended ant colony optimization for non-convex mixed integer nonlinear programming. Computers & Operations Research, 36(7), 2217 – 2229.

24-    Sepehri, M.M., & Rahimi moghadam, M. (2007). Ant colony and its application. farhang menhaj puplication.Tarbiyat modares university.

25-    Shil, H. Z., & XuG, J. (2004) .Ant Colony Optimization Algorithm with Random Perturbation behavior to the Problem of Optimal Unit Commitment with Probabilistic Spinning Reserve Determination. Elsevier Electric, Power Systems Research. 69, 295-303.

26-    Wang, Y., & Xie, J. (2000).Ant Colony Optimization for Multicast Routing. The 2000 IEEE Asian Pacific Conference on Circuits and Systems, IEEE Apcc as 2000, 54-57.

27-    Widmer, M., & Hertz, A. (1989). A new heuristic method for the flowshop sequencing problem. European Journal of Operational Research, 41(2), 186–193.

28-    Xiangyong Li, M.F., & Baki, Y.P. (2011). Flow shop scheduling to minimize the total completion time with a permanently present operator: Models and ant colony optimization metaheuristic. Computers & Operations Research 38(1), 152–164.

29-    Xing, L.N, & Chen, Y.W., & Wang, P. & Zhao, Q.S., & Xiong, J. A. (2010). Knowledge-Based Ant Colony Optimization for Flexible Job Shop Scheduling Problems. Applied Soft Computing, 10(3), 888–896.

30-    Yagmahan, B., & Mutlu, Y. M. (2010). A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications 37(2), 1361–1368.