Variable Neighborhood Search for Multi-Objective Parallel Machine Scheduling Problems

Among all types of production environment, identical parallel machines are frequently used to increase the manufacturing capacity in Taiwan printed circuit board (PCB) industries. In addition, multiple but conflicting objectives have to be considered when a manager plans the production scheduling. Compared to the single objective problem, the multiple-objective version no longer looks for an individual optimal solution; instead an approximated Pareto front consisting of a set of non-dominated solutions will be needed and established. The manager then can select one of the alternatives from the set. This research aims at employing a variable neighborhood search (VNS) algorithm to solve the identical parallel machine scheduling problem with two conflicting objectives: makespan and total tardiness. Two types of local search methods are defined insert a job to a different position or swap jobs among machines. In each of four neighborhoods formed, the neighboring solutions are generated using one of the two local search methods proposed and then are evaluated according to one of the objectives considered. All neighboring solutions are used to update the approximated Pareto front. The performance of the proposed algorithm is tested on a set of real data collected from a leading PCB factory in Taiwan. The computational results show that the proposed VNS algorithm outperforms two competing algorithms - SSA-SPGA and TWMGS in terms of solution quality and computational time.