Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times

• Published in: PloS one 2018-07, Vol.13 (7), p.e0200030-e0200030
• Main Authors: Ezugwu, Absalom E, Adeleke, Olawale J, Viriri, Serestina
• Format: Article
• Language: English
• Subjects: Algorithms; Analysis; Biology and Life Sciences; Civil engineering; Cloud computing; Computer science; Decoding; Dynamic loads; Ecology and Environmental Sciences; Genetic algorithms; Global optimization; Mathematics; Optimization; Optimization algorithms; Organisms; Physical Sciences; Population; Research and Analysis Methods; Scheduling; Search algorithms; Setup times; Social Sciences; Statistical analysis; Statistical tests; Traveling salesman problem
• ISSN: 1932-6203; 1932-6203
• DOI: 10.1371/journal.pone.0200030

This paper addresses the problem of makespan minimization on unrelated parallel machines with sequence dependent setup times. The symbiotic organisms search (SOS) algorithm is a new and popular global optimization technique that has received wide acceptance in recent years from researchers in continuous and discrete optimization domains. An improved SOS algorithm is developed to solve the parallel machine scheduling problem. Since the standard SOS algorithm was originally developed to solve continuous optimization problems, a new solution representation and decoding procedure is designed to make the SOS algorithm suitable for the unrelated parallel machine scheduling problem (UPMSP). Similarly, to enhance the solution quality of the SOS algorithm, an iterated local search strategy based on combining variable numbers of insertion and swap moves is incorporated into the SOS algorithm. More so, to further improve the SOS optimization speed and performance, the longest processing time first (LPT) rule is used to design a machine assignment heuristic that assigns processing machines to jobs based on the machine dynamic load-balancing mechanism. Subsequently, the machine assignment scheme is incorporated into SOS algorithms and used to solve the UPMSP. The performances of the proposed methods are evaluated by comparing their solutions with other existing techniques from the literature. A number of statistical tests were also conducted to determine the variations in performance for each of the techniques. The experimental results showed that the SOS with LPT (SOS-LPT) heuristic has the best performance compared to other tested method, which is closely followed by SOS algorithm, indicating that the two proposed algorithms' solution approaches are reasonable and effective for solving large-scale UPMSPs.