Mayfly Optimization Algorithm (MA): A population-based approach used for the Application of flow-shop scheduling problem

Join 376 other subscribers

1. Introduction Mayflies are insects that belong to the order Ephemeroptera, which is part of an ancient group of insects called Palaeoptera. It is estimated that there are over 3000 species of mayflies worldwide. Their name derives from the fact that they appear mainly during May in the UK [1]. The Mayfly optimation algorithm (MA)  benchmarked against seven high quality meta-heuristic optimization algorithms on 25 test functions which are classified in 3 groups (unimodal, multimodal and fixed dimension), multi-objective optimization and a discrete classic flow-shop scheduling problem [2]. Using those functions, the characteristics of exploitation and exploration of the method are tested. The results reveal that the MA method has superior performance to the most well-known metaheuristic optimization algorithms not only in local search but also in global search capabilities. Although the MA method is not always the fastest one among the methods to which the results are compared, it has a higher probability of finding a global optimum. The convergence behavior of the MA method is also exceptional, since most of the times it reaches the best overall solution in the early iterations. MA’s results are satisfactory to discrete problems as well as multi-objective optimization [3].

Fig 1: Mayfly Optimization Algorithm (MA)

2. The Mayfly

Mayfly is flattened and has 3 hair-like tails on the tips of their abdomens, along with leafy gills all along the sides of their abdomens. Unlike adults, mayfly naiads have chewing mouth parts. As with all insects, mayflies have 6 legs, 3 body parts, and 2 antennae. Mayflies exhibit a number of ancestral traits that were probably present in the first flying insects, such as long tails and wings that do not fold flat over the abdomen [4]. Their immature stages are aquatic fresh water forms (called “naiads” or “nymphs”), whose presence indicates a clean, unpolluted environment. They are unique among insect orders in having a fully winged terrestrial preadult stage, the subimago, which moults into a sexually mature adult, the imago [5].

Fig 2: The mayfly

3. Inspiration of MA

The main inspired of Mayfly optimization Algorithm is from the behavior of adult mayflies, including the processes of crossover, mutation, gathering in swarm, nuptial dance, and random walk After hatching from the egg, immature mayflies are visible to the naked eye and they spend several years growing as aquatic nymphs, until they are ready to ascend to the surface as adults [6]. An adult mayfly lives only for a couple of days, until it fulfills its final goal to breed. To attract females, most of male adults congregate in swarms a few meters above water, performing a nuptial dance, through characteristic up-and-down patterns of movement. Females fly into these swarms, in order to mate with a male in the air. Mating may last just a few seconds and when it is completed females drop their eggs onto the surface of water, and their life cycle goes on [7]. The latter two constitute the main advantages of the purposed method, which enhance exploration. Moreover, through this research, it was found that by using two different equations for each population (males and females), the exploration is improved. Mayflies spend an entire year in freshwater in what’s known as a nymph stage, in which the insects already look much like their adult forms but don’t actually do anything. After that year, the insects fly off to find a mate, lay some eggs, and promptly die [8].

Fig 3: Inspiration of MO

4. Swarming Mayfly: Interaction of Polarized and Unpolarized Light Pollution

Fig 4: Interaction of Polarized and Unpolarized Light Pollution in Mayfly

Nocturnal artificial sources of unpolarized and horizontally polarized light interact to attract polar tactic insects. Unpolarized light sources (e.g., street-lamps) may attract perching or flying nocturnal polar tactic insects directly (Ephoron virgo know as mayfly illustrated). Alternatively, unpolarized light from the street-lamp can become horizontally polarized through reflection from smooth, dark surfaces like asphalt, simulating the appearance of a water body. Mayfly is independently attracted to both unpolarized and polarized light sources that both types of photo pollution are being produced at the bridge, and that spatial patterns of swarming and ovipositor are consistent with evolved behaviors being triggered maladaptive by these two types of light pollution [9]. We suggest solutions to bridge and lighting design that should prevent or mitigate the impacts of such scenarios in the future. The detrimental impacts of such scenarios may extend beyond mayfly.

5. Numerical Expression of MA

Initially, two sets of mayflies are randomly generated, representing the male and female population respectively. That is, each mayfly is randomly placed in the problem space as a candidate solution represented by a dim-dimensional vector

6. Flowchart of MA

Fig 5: Flowchart of MA

7. Real-world problem: To test MA’s accuracy and efficiency

Fig 6: Applications of MA

To test MA’s accuracy and efficiency in discrete, as well as real engineering problems, we compared its performance using a classic flow-shop scheduling problem. Flow shop scheduling problems, are a class of scheduling problems with a workshop, proposed by Johnson (1954). In a flow shop scheduling problem, there is a set of jobs or tasks to be processed in a set of 𝑛 𝑚 machines or processors in the same order. At any time, each job can be processed on at most one machine and each machine can process at most one job. Furthermore, once a job is processed on a machine, it cannot be terminated before it is completed [12]. The objective is to find a sequence for the processing of the jobs in the machines so that a given criterion is optimized, with the most common criterion  being the minimization of the, the completion time for the n-job, m-machine problem is calculated.

Flow Scheduling is an alternative method for production scheduling and execution [13]. Flow Scheduling is latest production execution model designed for simple production scheduling and reporting. It allows you to assign finished goods or semi finished goods to production lines / areas, schedule production of your lines from demand, and understand resource consumption based on production load and times [14]. You no longer have to create individual work orders or orders for production reporting. You just need to create the production requirements by day or shift and report by item and production line. Flow Scheduling allows you to:

  • Set up schedule periods
  • Flow Rates
  • Item Production Data
  • Flow Schedule Orders 
  • Flex Fences 
  • Production Reporting

Thus the MA’s performance is also assessed through convergence behavior in multi-objective optimization as well as using a real-world discrete flow-shop scheduling problem [15].  It is used in place of standard Work Orders or Advanced Repetitive to drive firm demand to your shop floor and record activity. It is appropriate for a company that is working in a Lean fashion or is looking to become Lean. For environments that utilize push / pull systems or Kanban this package may help you reduce overhead associated with creation of work schedules and reporting [16].

8. Advantages & Disadvantages of MA

The advantages and disadvantages about MA is below describe under the figure as follows

Fig 7: Advantages & limitations of MA

Reference

[1]O. Abedinia, N. Amjady and A. Ghasemi, “A new metaheuristic algorithm based on shark smell optimization”, Complexity, vol. 21, no. 5, pp. 97-116, 2014. Available: 10.1002/cplx.21634 [Accessed 4 November 2020].

[2]J. Allan and A. Flecker, “The mating biology of a mass-swarming mayfly”, Animal Behaviour, vol. 37, pp. 361-371, 1989. Available: 10.1016/0003-3472(89)90084-5 [Accessed 4 November 2020].

[3]A. Askarzadeh, “A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm”, Computers & Structures, vol. 169, pp. 1-12, 2016. Available: 10.1016/j.compstruc.2016.03.001 [Accessed 4 November 2020].

[4]A. Askarzadeh, “A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm”, Computers & Structures, vol. 169, pp. 1-12, 2016. Available: 10.1016/j.compstruc.2016.03.001 [Accessed 4 November 2020].

[5]S. Báez, F. Angel-Bello, A. Alvarez and B. Melián-Batista, “A hybrid metaheuristic algorithm for a parallel machine scheduling problem with dependent setup times”, Computers & Industrial Engineering, vol. 131, pp. 295-305, 2019. Available: 10.1016/j.cie.2019.03.051 [Accessed 4 November 2020].

[6]A. Baykasoğlu and Ş. Akpinar, “Weighted Superposition Attraction (WSA): A swarm intelligence algorithm for optimization problems – Part 1: Unconstrained optimization”, Applied Soft Computing, vol. 56, pp. 520-540, 2017. Available: 10.1016/j.asoc.2015.10.036 [Accessed 4 November 2020].

[7]C. Coello, G. Pulido and M. Lechuga, “Handling multiple objectives with particle swarm optimization”, IEEE Transactions on Evolutionary Computation, vol. 8, no. 3, pp. 256-279, 2004. Available: 10.1109/tevc.2004.826067 [Accessed 4 November 2020].

[8]K. Deb and H. Jain, “An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints”, IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp. 577-601, 2014. Available: 10.1109/tevc.2013.2281535 [Accessed 4 November 2020].

[9]K. Deb and H. Jain, “An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints”, IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp. 577-601, 2014. Available: 10.1109/tevc.2013.2281535 [Accessed 4 November 2020].

[10]G. Dhiman and V. Kumar, “Spotted hyena optimizer: A novel bio-inspired based metaheuristic technique for engineering applications”, Advances in Engineering Software, vol. 114, pp. 48-70, 2017. Available: 10.1016/j.advengsoft.2017.05.014 [Accessed 4 November 2020].

[11]G. Davies, “‘Dragonflies and Damselflies of South Africa.’ Michael J. Samways. ‘DRAGONFLIES AND DAMSELFLIES OF SOUTH AFRICA.’ Michael J. Samways. Sofia/Moscow: Pensoft Publishers, 2008 . 297 pp., 22.5×14 cm. Softcover. ISBN 978-954-642-330-6. Price: 39 Euro. Available from: PENSOFT Publishers, Geo Milev Str. 13, 1111 Sofia, Bulgaria; Tel.: +359-2-967-40-70, Fax: +359-2-967-40-71; e-mail: info@pensoft.net or pensoft@mbox.infotel.bg; Pensoft Online Bookshop: http://www.pensoft.net.”, African Invertebrates, vol. 49, no. 2, pp. 233-234, 2008. Available: 10.5733/afin.049.0212.

[12]R. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory”, MHS’95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Available: 10.1109/mhs.1995.494215 [Accessed 4 November 2020].

[13]Z. Fan, Y. Fang, W. Li, Y. Yuan, Z. Wang and X. Bian, “LSHADE44 with an Improved Constraint-Handling Method for Solving Constrained Single-Objective Optimization Problems”, 2018 IEEE Congress on Evolutionary Computation (CEC), 2018. Available: 10.1109/cec.2018.8477943 [Accessed 4 November 2020].

[14]Y. Feng, B. Zheng and Z. Li, “Exploratory study of sorting particle swarm optimizer for Multiobjective design optimization”, Mathematical and Computer Modelling, vol. 52, no. 11-12, pp. 1966-1975, 2010. Available: 10.1016/j.mcm.2010.04.020 [Accessed 4 November 2020].

[15]F. Glover, “Future paths for integer programming and links to artificial intelligence”, Computers & Operations Research, vol. 13, no. 5, pp. 533-549, 1986. Available: 10.1016/0305-0548(86)90048-1 [Accessed 4 November 2020].

[16]B. Addis, A. Cassioli, M. Locatelli and F. Schoen, “A global optimization method for the design of space trajectories”, Computational Optimization and Applications, vol. 48, no. 3, pp. 635-652, 2009. Available: 10.1007/s10589-009-9261-6 [Accessed 4 November 2020].

Join 376 other subscribers

Leave a Reply to shilkaren Cancel reply

%d bloggers like this: