Hybrid Ant Colony Optimization-Genetics Algorithm to Minimize Makespan Flow Shop Scheduling

  • Authors

    • Jonas Franky R. Panggabean
    2018-03-05
    https://doi.org/10.14419/ijet.v7i2.2.11868
  • Flow shop scheduling, Ant Colony Optimization Algorithm (ACO), Genetics and Hybrids

  • Flow shop scheduling is a scheduling model in which the job to be processed entirely flows in the same product direction / path. In other words, jobs have routing work together. Scheduling problems often arise if there is n jobs to be processed on the machine m, which must be specified which must be done first and how to allocate jobs on the machine to obtain a scheduled production process. In research of Zini, H and ElBernoussi, S. (2016) NEH Heuristic and Stochastic Greedy Heuristic (SG) algorithms. This paper presents modified harmony search (HS) for flow shop scheduling problems with the aim of minimizing the maximum completion time of all jobs (makespan). To validate the proposed algorithm this computational test was performed using a sample dataset of 60 from the Taillard Benchmark. The HS algorithm is compared with two constructive heuristics of the literature namely the NEH heuristic and stochastic greedy heuristic (SG). The experimental results were obtained on average for the dataset size of 20 x 5 to 50 x 10, that the ACO-GA algorithm has a smaller makespan than the other two algorithms, but for large-size datasets the ACO-GA algorithm has a greater makespan of both algorithms with difference of 1.4 units of time.

  • References

    1. [1] H. Bräsel, A. Herms, M. Mörig, T. Tautenhahn, J. Tusch, and F. Werner, “Heuristic constructive algorithms for open shop scheduling to minimize mean flow time,†Eur. J. Oper. Res., vol. 189, no. 3, pp. 856–870, 2008.

      [2] M. Nejati, I. Mahdavi, R. Hassanzadeh, N. Mahdavi-Amiri, and M. Mojarad, “Multi-job lot streaming to minimize the weighted completion time in a hybrid flow shop scheduling problem with work shift constraint,†Int. J. Adv. Manuf. Technol., vol. 70, no. 1–4, pp. 501–514, 2014.

      [3] K. Kouser and A. Priyam, “Feature selection using genetic algorithm for clustering high dimensional data,†Int. J. Eng. Technol., vol. 7, no. 2, pp. 27–30, 2018.

      [4] R. Rahim, I. Zulkarnain, and H. Jaya, “Double hashing technique in closed hashing search process,†IOP Conf. Ser. Mater. Sci. Eng., vol. 237, no. 1, p. 12027, Sep. 2017.

      [5] R. H. Ahmadi and U. Bagchi, “Improved lower bounds for minimizing the sum of completion times of n jobs over m machines in a flow shop,†Eur. J. Oper. Res., vol. 44, no. 3, pp. 331–336, 1990.

      [6] I. Ribas, R. Companys, and X. Tort-Martorell, “Efficient heuristics for the parallel blocking flow shop scheduling problem,†Expert Syst. Appl., vol. 74, pp. 41–54, 2017.

      [7] S. Agrawal., A. Gautam, D. K. Chauhan, L. M. Tiwari, and S. Kapoor, “A flow shop scheduling problem with transportation time and separated setup time of jobs,†in Procedia Engineering, 2012, vol. 38, pp. 1327–1332.

      [8] X. Zhang and S. Van De Velde, “Approximation algorithms for the parallel flow shop problem,†Eur. J. Oper. Res., vol. 216, no. 3, pp. 544–552, 2012.

      [9] A. S. Ahmar et al., “Modeling Data Containing Outliers using ARIMA Additive Outlier (ARIMA-AO),†J. Phys. Conf. Ser., vol. 954, no. 1, 2018.

      [10] B. Nair B J and R. Reghunath, “Coding and functional defect region prediction of placental protein in an embryo cell of first trimester using ANN approach,†Int. J. Eng. Technol., vol. 7, no. 1–9, p. 167, Mar. 2018.

      [11] U. Khair, H. Fahmi, S. Al Hakim, and R. Rahim, “Forecasting Error Calculation with Mean Absolute Deviation and Mean Absolute Percentage Error,†J. Phys. Conf. Ser., vol. 930, no. 1, p. 12002, Dec. 2017.

      [12] D. R Vora and K. Iyer, “EDM – survey of performance factors and algorithms applied,†Int. J. Eng. Technol., vol. 7, no. 2–6, p. 93, Mar. 2018.

      [13] C. Saranya Jothi, V. Usha, and R. Nithya, “Particle swarm optimization to produce optimal solution,†Int. J. Eng. Technol., vol. 7, no. 1.7 Special Issue 7, pp. 210–216, 2018.

      [14] R. Rahim, Nurjamiyah, and A. R. Dewi, “Data Collision Prevention with Overflow Hashing Technique in Closed Hash Searching Process,†J. Phys. Conf. Ser., vol. 930, no. 1, p. 12012, Dec. 2017.

      [15] W. Yu, Z. Liu, L. Wang, and T. Fan, “Routing open shop and flow shop scheduling problems,†Eur. J. Oper. Res., vol. 213, no. 1, pp. 24–36, 2011.

      [16] C. M. V. S. Prasad, K. R. Rao, D. S. Kumar, and A. V. Prabhu, “Performance evaluation of power optimization in wireless sensor networks using particle swarm optimization,†Int. J. Eng. Technol., vol. 7, pp. 404–408, 2018.

      [17] R. Rahim, I. Zulkarnain, and H. Jaya, “A review: search visualization with Knuth Morris Pratt algorithm,†in IOP Conference Series: Materials Science and Engineering, 2017, vol. 237, no. 1, p. 12026.

      [18] D. Shabtay, “The just-in-time scheduling problem in a flow-shop scheduling system,†Eur. J. Oper. Res., vol. 216, no. 3, pp. 521–532, 2012.

      [19] R. Rahim, S. Nurarif, M. Ramadhan, S. Aisyah, and W. Purba, “Comparison Searching Process of Linear, Binary and Interpolation Algorithm,†J. Phys. Conf. Ser., vol. 930, no. 1, p. 12007, Dec. 2017.

      [20] D. Abdullah, R. Rahim, D. Apdilah, S. Efendi, T. Tulus, and S. Suwilo, “Prime Numbers Comparison using Sieve of Eratosthenes and Sieve of Sundaram Algorithm,†in Journal of Physics: Conference Series, 2018, vol. 978, no. 1, p. 12123.

      [21] C. Rajendran and H. Ziegler, “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs,†Eur. J. Oper. Res., vol. 155, no. 2, pp. 426–438, Jun. 2004.

      [22] Quang Chieu Ta, J.-C. Billaut, and J.-L. Bouquard, “Heuristic algorithms to minimize the total tardiness in a flow shop production and outbound distribution scheduling problem,†in 2015 International Conference on Industrial Engineering and Systems Management (IESM), 2015, pp. 128–134.

      [23] M. H. Aghdam and P. Kabiri, “Feature selection for intrusion detection system using ant colony optimization,†Int. J. Netw. Secur., vol. 18, no. 3, pp. 420–432, 2016.

      [24] G. F. Deng and W. T. Lin, “Ant colony optimization-based algorithm for airline crew scheduling problem,†Expert Syst. Appl., vol. 38, no. 5, pp. 5787–5793, 2011.

      [25] M. Verma, M. Gupta, B. Pal, and K. K. Shukla, “A stochastic greedy heuristic algorithm for the orienteering problem,†in Proceedings - 5th IEEE International Conference on Computer and Communication Technology, ICCCT 2014, 2015, pp. 59–65.

  • Downloads

  • How to Cite

    Panggabean, J. F. R. (2018). Hybrid Ant Colony Optimization-Genetics Algorithm to Minimize Makespan Flow Shop Scheduling. International Journal of Engineering & Technology, 7(2.2), 40-44. https://doi.org/10.14419/ijet.v7i2.2.11868