|
Abstract: Open
shop scheduling is an important scheduling problem and has wide
engineering applications in manufacturing. Optimization algorithms are
important research content in scheduling theory. Artificial intelligence
based meta-heuristic algorithms are effective methods for this problem.
A new meta-heuristic based on particle swarm optimization (PSO) is
proposed to obtain optimized open shop schedule. First, the limitation
of information sharing mechanism in PSO model is discussed, and then new
information sharing mechanism based on swarm intelligence is put
forward. Based on the new information sharing mechanism, a new PSO based
on scheduling algorithm–PSO-OSP is proposed. The proposed algorithm
utilizes neighborhood knowledge to direct its local search procedure
which can overcome the blindness or randomness introduced by
meta-heuristics. Finally, OSP benchmarks are used to test its
efficiency. Simulation results show that the new proposed algorithm can
improve the convergence speed and obtain optimized open shop schedules.
Key
words: Open
shop scheduling Particle swarm optimization Information sharing
mechanism Neighborhood knowledge
CLC No: TP38
国家自然科学基金资助项目(50305008). Received 20050214,
received in revised form 20050801
|