A two-stage particle swarm algorithm for multi-objective job shop scheduling problems | |
| Author | Thongchai Pratchayaborirak |
| Call Number | AIT Thesis no.ISE-07-08 |
| Subject(s) | Production scheduling Computer algorithms |
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of Engineering in Industrial Engineering & Management, School of Engineering and Technology |
| Publisher | Asian Institute of Technology |
| Series Statement | Thesis ; no. ISE-07-08 |
| Abstract | This thesis introduces a two-stage particle swarm optimization algorithm (2ST-PSG) for multi-objective job shop scheduling problem. The three objectives considered in this research are: minimize makespan, minimize total weighted earliness and minimize total weighted tardiness. The goal is to find optimal or near optimal solution for the combined objectives. The proposed algorithm is divided into two stages. The first stage of the algorithm consists of 4 swarms which are serially executed using the same objective function. When a certain swarm is terminated, a percentage of particles will be randomly selected to migrate to the next swarm to join with the newly generated particles. This can help boost the convergence of solution by using information from the previous swarm. The first stage ends when the fourth swarm is terminated. In the second stage, equal numbers of particles are randomly selected from the four previous swarms to form a single swarm and the PSO algorithm is repeated until the stopping condition is met. The best result yields at the end of the second stage will be used as the best answer found. The 2ST-PSO is evaluated by using the benchmark problems provided by OR-Library and compared with best known results from published works for both single and multi¬objective cases. The proposed particle swarm algorithm can efficiently find good solutions in both single and multi-objective job shop scheduling problem. Moreover, the proposed algorithm discovers 10 new best known solutions for single-objective cases with weighted tardiness objective. For multi-criteria cases, the experimental result illustrates that the proposed algorithm is efficient and effective for solving the multi-objective problems in terms of computational time and solution quality; especially for larger problem size |
| Year | 2007 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. ISE-07-08 |
| 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;Pisut Koomsap; |
| Scholarship Donor(s) | Asian Institute of Technology Fellowship; |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 2007 |