Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times
Open Access
- 5 July 2018
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 13 (7) , e0200030
Abstract
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.Keywords
This publication has 39 references indexed in Scilit:
- An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup timesComputers & Operations Research, 2012
- Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulationInformation Sciences, 2011
- Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup timesApplied Soft Computing, 2011
- Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristicExpert Systems with Applications, 2010
- Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithmExpert Systems with Applications, 2009
- Semiconductor manufacturing scheduling of jobs containing multiple orders on identical parallel machinesInternational Journal of Production Research, 2009
- A discrete particle swarm optimization algorithm for scheduling parallel machinesComputers & Industrial Engineering, 2009
- A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machinesInternational Journal of Production Economics, 2008
- An exact algorithm for the identical parallel machine scheduling problemEuropean Journal of Operational Research, 2004
- A cutting plane algorithm for the unrelated parallel machine scheduling problemEuropean Journal of Operational Research, 2002