Hybrid particle swarm optimizers in the single machine scheduling problem: an experimental study

Abstract

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 on a specific scheduling problem: the Single Machine Total Weighted Tardiness): a Hybrid PSO (HPSO), a Hybrid PSO with a simple neighborhood topology (HPSOneigh) and a new version that adds problem-specific knowledge to HPSOneigh (HPSOkn). 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 HPSOkn 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.