Particle swarm algorithm for job shop scheduling problems | |
| Author | Luksamee Rookkapibal |
| Call Number | AIT Thesis no.ISE-06-12 |
| Subject(s) | Production scheduling Computer algorithms |
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of Engineering, School of Engineering and Technology |
| Publisher | Asian Institute of Technology |
| Series Statement | Thesis ; no. ISE-06-12 |
| Abstract | PSO is a metaheuristic based on probabilistic search approach. It mimics the social behavior of birds flock that fly through the problem hyperspace. During the search, each particle learns and moves to new position by using both its own experience and experience shared from other particles. The advantages of PSO are that the algorithm is easy to understand and easy to implement. This thesis presents particle swarm optimization (PSO) algorithm for job shop scheduling problem (JSP). The objective is to evolve an optimal or near optimal schedule with a minimization criterion e.g. makespan or total weighted tardiness. In this study, a standard PSO algorithm is proposed along with schemes to decode the position of particle into a valid schedule. The PSO algorithm is combined with a local search and re-initialization strategy to enhance the efficiency of the search. The re¬initialization is used to maintain the diversity during the search to avoid being trapped in a local area while the local search is incorporated to locally improve solutions. Performance of the proposed algorithm is tested against some well known benchmark instances. The experimental result shows that PSO is efficient for solving large scale problems with reasonable quality and computational time |
| Year | 2006 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. ISE-06-12 |
| Type | Thesis |
| School | School of Engineering and Technology (SET) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Industrial Systems Engineering (ISE) |
| Chairperson(s) | Voratas Kachitvichyanukul; |
| Examination Committee(s) | Huynh Trung Luong;Honda, Kiyoshi; |
| Scholarship Donor(s) | Asian Development Bank-Japan Scholarship Program (ADB-JSP); |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 2006 |