A Multiobjective Optimization Approach to Solve a Parallel Machines Scheduling Problem

Abstract EN

A multiobjective optimization problem which focuses on parallel machines scheduling is considered.

This problem consists of scheduling n independent jobs on m identical parallel machines with release dates, due dates, and sequence-dependent setup times.

The preemption of jobs is forbidden.

The aim is to minimize two different objectives: makespan and total tardiness.

The contribution of this paper is to propose first a new mathematical model for this specific problem.

Then, since this problem is NP hard in the strong sense, two well-known approximated methods, NSGA-II and SPEA-II, are adopted to solve it.

Experimental results show the advantages of NSGA-II for the studied problem.

An exact method is then applied to be compared with NSGA-II algorithm in order to prove the efficiency of the former.

Experimental results show the advantages of NSGA-II for the studied problem.

Computational experiments show that on all the tested instances, our NSGA-II algorithm was able to get the optimal solutions.