Solving Machine Scheduling Problem Using Particle Swarm Optimization Method

Abstract

In this paper the problem of scheduling n jobs in a single machine is considered to minimize the total cost of sum weighted completion time, maximum weighted lateness and maximum penalty earliness (i,e to minimize the multiple objective functions ( )). The Particle Swarm Optimization (PSO) methods are applied as new local search method on a set of randomly generated problems to solve machine scheduling problem with multiple objective functions. Comparison studies are made between PSO and Genetic Algorithm (GA) to show which one is the better method in applications. In addition, tuning the parameters of every method has been suggested in order to improve the application of every method. A new style of development steps has been proposed to achieve good convergence in application. Since our problem is NP-hard, we propose a new heuristic method like particle swarm optimization to find near optimal solutions specially when the number of jobs exceed the ability of some exact methods like Branch and Bound Methods (BAB) in solving such problems.
Last, the two proposed local search methods results are compared with complete search method in solving problem like machines scheduling problem. Computational experience found that these local search algorithms solve problem to 2000 jobs with reasonable time.