A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines

• Unrelated parallel machines scheduling problem with past-sequence-dependent setup times, release dates, deteriorating jobs and learning effects is presented.
• The objective is to determine jointly the jobs assigned to each machine and the order of jobs such that the total machine load is minimized.
• An efficient hybrid meta-heuristic (PSO-GA) approach is presented.

This paper dealt with an unrelated parallel machines scheduling problem with past-sequence-dependent setup times, release dates, deteriorating jobs and learning effects, in which the actual processing time of a job on each machine is given as a function of its starting time, release time and position on the corresponding machine. In addition, the setup time of a job on each machine is proportional to the actual processing times of the already processed jobs on the corresponding machine, i.e., the setup times are past-sequence-dependent (p-s-d). The objective is to determine jointly the jobs assigned to each machine and the order of jobs such that the total machine load is minimized. Since the problem is NP-hard, optimal solution for the instances of realistic size cannot be obtained within a reasonable amount of computational time using exact solution approaches. Hence, an efficient method based on the hybrid particle swarm optimization (PSO) and genetic algorithm (GA), denoted by HPSOGA, is proposed to solve the given problem. In view of the fact that efficiency of the meta-heuristic algorithms is significantly depends on the appropriate design of parameters, the Taguchi method is employed to calibrate and select the optimal levels of parameters. The performance of the proposed method is appraised by comparing its results with GA and PSO with and without local search through computational experiments. The computational results for small sized problems show that the mentioned algorithms are fully effective and viable to generate optimal/near optimal solutions, but when the size of the problem is increased, the HPSOGA obtains better results in comparison with other algorithms.

Figure optionsDownload as PowerPoint slide