CPSO-Based Hybrid Approach for Scheduling Parallel Machines with Processing Set Restrictions

We consider identical parallel machine scheduling problem where every job is only allowed to be processed on a specified subset of machines. We develop an efficient CPSO (chaotic particle swarm optimization) based hybrid approach to solve the above problem with the objective of minimizing total number of tardy jobs. In the proposed approach, the problem is firstly decomposed into a machine assignment subproblem and a job sequencing subproblem, then the job sequencing subproblem is solved optimally by a heuristic algorithm with the time complexity of O(mnlogn), and the machine assignment subproblem is solved by the proposed CPSO algorithm, in which the problem characteristics are incorporated to enhance the performance of exploration and exploitation in the proposed algorithm. Numerical computations show that the proposed hybrid approach outperforms several other methods on the studied problems.