Hybrid particle swarm optimizers in the single machine scheduling problem: An experimental study. (English) Zbl 1200.90065

Dahal, Keshav P. (ed.) et al., Evolutionary scheduling. Berlin: Springer (ISBN 978-3-540-48582-7/hbk). Studies in Computational Intelligence 49, 143-164 (2007).
Summary: Although Particle Swarm Optimizers (PSO) have been successfully used in a wide variety of continuous optimization problems, their use has not been as widespread in discrete optimization problems, particularly when adopting non-binary encodings. In this chapter, we discuss three PSO variants (which are applied to a specific scheduling problem: the Single Machine Total Weighted Tardiness): a Hybrid PSO (HPSO), a Hybrid PSO with a neighborhood topology (HPSO\(_{\text{neigh}}\)) and a new version that adds problem-specific knowledge to HPSO\(_{\text{neigh}}\) (HPSO\(_{\text{kn}}\)). The last approach is used to guide the blind search that PSO usually does and reduces its computational cost (measured in terms of the objective function evaluations performed). It is also shown that HPSO\(_{\text{kn}}\) obtains good results with a lower computational cost, when comparing it against the other PSO versions analyzed, and with respect to a classical PSO approach and to a multirecombined evolutionary algorithm (MCMP-SRI-IN), which contains specialized operators to tackle single machine total weighted tardiness problems.
For the entire collection see [Zbl 1110.90002].


90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming


Tabu search
Full Text: DOI