To search, Click below search items.


All Published Papers Search Service


Multi-Processor Tasks with Resource and Timing Constraints Using Particle Swarm Optimization


Tzu-Chiang Chiang, Po-Yin Chang, Yueh-Min Huang


Vol. 6  No. 4  pp. 71-77


The job-shop scheduling problems have been categorized as NP-complete problems. In our previous work, we use Hopfield Neural Network (HNN) to solve the energy function of the scheduling multi-processor tasks problem. Particle swarm optimization (PSO) is an evolutionary computation technique mimicking the behavior of flying birds and their means of information exchange. However, a pure PSO algorithm approach tends to solve continues linear problems. Therefore, the pure PSO algorithm need to be specially designed or some other methods may be combined to solve the energy function. This paper proposes using the particle swarm optimization to solve the constrained scheduling problem in display system operation. The constrained scheduling problem not only satisfies the resource constraint and the timing constraint. In our work, there are barriers must be overcome in applying energy function to PSO. In particle encoding, we attempt using a one-dimension 0-1 array mapping a three-dimension matrix of a candidate solution for each particle, and then using sigmoid function to produce probability threshold from velocity of each particle for velocity updating. The result showed that the proposed approach is capable of obtaining higher quality solution efficiently in constrained scheduling problems.


Job-shop scheduling, Particle swarm optimization, Energy function